Best Time to Buy and Sell Stock II — Popular Coding Interview Question
In this post, we will explore solution to another most popular coding interview question about buying and selling stocks to make maximum profit.
This problem is a variation of the problem Best Time to Buy and Sell Stock I discussed earlier.
Problem Statement
An array of integers named prices
is provided, representing the daily price of a specific stock, where prices[i]
corresponds to the stock's price on day i
.
Each day, you have the option to either purchase and/or sell this stock, with the restriction that you can possess no more than one share at any given moment. Nevertheless, it is permissible to buy and sell the stock within the same day.
Your task is to determine and return the highest possible profit from these transactions.
Understanding the Problem Statement
- The goal is to maximize profit from buying and selling stocks given their daily prices.
- You can perform as many transactions as you want (buy one and sell one share of the stock multiple times).
- You cannot hold more than one share of the stock at any given time (must sell the stock before you buy again).
- Buying and selling on the same day is allowed.
Example:
Input: prices = [7,1,5,3,6,4] Output: 7
Explanation: The optimal transactions are as follows:
- Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 4.
- Buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 3. Total profit = 4 + 3 = 7.
Brute Force Approach
For this problem, a brute force approach would involve checking all possible sequences of buy-sell operations and calculating the total profit for each. This means for every day, deciding whether to buy, sell, or do nothing, and then exploring all possible outcomes.
- Use nested loops: The outer loop starts on the first day, and for every day, the inner loop explores selling on every subsequent day.
- Calculate profit for every buy-sell pair and sum them up to find the total profit for all transactions.
This approach has a significant downside: it’s extremely inefficient, with a time complexity of O(2^n), where n is the number of days. This is because for each day, you have two choices (to transact or not), leading to an exponential number of combinations.
Optimal Solution
You might notice that the maximum profit comes from adding all positive differences between consecutive days. This observation is key to transitioning from a brute force approach to a more optimal solution.
The key insight is that the sum of all positive gains (selling price — buying price) from each transaction equals the total maximum profit. This is because:
- Profit from any subsequence: If you have a sequence of prices that goes up and then down, buying at the start of the sequence and selling at the end of the increasing sequence before it goes down maximizes profit for that particular subsequence.
- Combining subsequences: If you repeat this process for every up-and-down sequence (every local minimum to local maximum), you effectively capture every opportunity to make a profit.
Consider a price pattern over five days: [1, 2, 3, 4, 5]. The optimal strategy is to buy on day 1 and sell on day 5, yielding a profit of 4. Notice that this profit (4) is the sum of all daily profits (1+1+1+1) obtained by buying and selling on each consecutive day.
The idea is to leverage the fact that for any three consecutive days, if prices go up from day 1 to day 2, and from day 2 to day 3, the profit from buying on day 1 and selling on day 3 is the same as the sum of the profits from buying on day 1 and selling on day 2, and then buying on day 2 and selling on day 3.
This property holds true for any longer sequence of increasing prices, meaning that we don’t need to identify the overall highest and lowest points; we only need to capture every small positive change.
Java Code:
public class Solution {
public int maxProfit(int[] prices) {
// Initialize a variable to keep track of the maximum profit
int maxProfit = 0;
// Iterate over each day in the prices array, except the last day
for (int i = 0; i < prices.length - 1; i++) {
// If the price of the stock on the next day is higher than the price on the current day
if (prices[i] < prices[i + 1]) {
// Calculate the profit from buying on the current day and selling on the next day
// Add this profit to the total maximum profit
maxProfit += prices[i + 1] - prices[i];
}
}
// After iterating through all the days, return the total maximum profit
return maxProfit;
}
}
Time and Space Complexity
- Time Complexity: O(n), where n is the number of days. This is because you’re passing through the array only once, making comparisons as you go.
- Space Complexity: O(1). The space required does not scale with the input size. You’re using a fixed amount of extra space (for the
maxProfit
variable).
Greedy Approach
This problem is a classic example where a greedy approach works perfectly. A greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. Here, taking every positive daily profit without considering future prices is the most immediate benefit and leads to the global maximum profit.
Conclusion
The reason this approach works so efficiently for this problem is it aligns perfectly with the problem’s inherent characteristics: transactions are unlimited, and capturing every incremental gain leads to the maximum overall profit. This simplifies the problem from needing to forecast or plan complex transactions to simply acting on immediate opportunities, ensuring no potential profit is missed.
If you found this post useful, please follow me on Medium. More to come!