Best Time to Buy and Sell Stock II
Problem Description
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Explanation:
- Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
- Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
- Total profit is 4 + 3 = 7.
Example 2:
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.
Example 3:
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints:
- 1 <= prices.length <= 3 * 104
- 0 <= prices[i] <= 104
Approaches
1. Greedy Approach
Intuition:
The problem is essentially about finding opportunities to make as much profit as possible by buying stocks on one day and selling them on another. This can be achieved by making transactions whenever there's a profit to be made, without concern for a future decrement in prices.
In a simplified manner, the problem reduces to accumulating all positive differences between consecutive days. By always projecting into the future and accumulating possible gains daily, we capitalize on every rising curve of the stock price graph.
Code:
- Time Complexity: O(n) since iterating through the prices array once.
- Space Complexity: O(1) since uses constant space.
Example Walkthrough:
2. Peak Valley Approach
Another way to look at this problem is to find every consecutive pair of peaks and valleys. A peak-to-valley traversal adds the difference from each peak to its preceding valley to determine the overall profit through multiple transactions.
Intuition:
This approach mimics the real-world scenario of buying stock at valleys (local minimums) and selling it at peaks (local maximums). This enables capturing every increasing sequence even if the overall curve spans over several days.
Code:
- Time Complexity: O(n) since iterating through the prices array once.
- Space Complexity: O(1) since uses constant space.