Best Time to Buy and Sell Stock II

MEDIUM

Description

You are given an integer array prices where prices[i] is the price of a given stock on the i^th 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:

Input: prices = [7,1,5,3,6,4]
Output: 7
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:

Input: prices = [1,2,3,4,5]
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:

Input: prices = [7,6,4,3,1]
Output: 0
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 * 10⁴
0 <= prices[i] <= 10⁴

Approaches

Checkout 3 different approaches to solve Best Time to Buy and Sell Stock II. Click on different approaches to view the approach and algorithm in detail.

Greedy Approach (Peak Valley)

This is the most efficient and intuitive approach. The key insight is that the total profit from a series of transactions is the sum of profits from individual, consecutive upward price movements. We can simply accumulate all positive gains from one day to the next.

Algorithm

Initialize maxProfit = 0.
Iterate through the prices array from the second element (i = 1 to n-1).
For each day i, check if the price is higher than the previous day's price (prices[i] > prices[i-1])
If it is, add the difference prices[i] - prices[i-1] to maxProfit.
After the loop finishes, maxProfit will hold the maximum possible profit.

The problem allows us to buy and sell on the same day. This flexibility means we don't have to worry about finding the absolute lowest valley and highest peak over a long period. Instead, we can focus on short-term gains.

Consider a price sequence a, b, c. The profit from buying at a and selling at c is c - a. This is mathematically equivalent to (b - a) + (c - b). This implies that we can decompose a single large profitable transaction into a series of smaller, day-to-day profitable transactions.

Therefore, the strategy is to iterate through the prices and whenever we see an increase from day i-1 to day i (i.e., prices[i] > prices[i-1]), we "transact" and add the profit prices[i] - prices[i-1] to our total.

This is a greedy approach because at each step, we make the locally optimal choice of taking any available profit, and this leads to the globally optimal solution. This approach is also equivalent to a space-optimized version of the dynamic programming solution.

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1]) {
                maxProfit += prices[i] - prices[i-1];
            }
        }
        return maxProfit;
    }
}

Complexity Analysis

Time Complexity: O(n)Space Complexity: O(1)

Pros and Cons

Pros:

Highly efficient with linear time and constant space.
The logic is simple and easy to implement.

Cons:

This specific greedy strategy works because of the problem's allowance for unlimited transactions. It might not be applicable to other stock problems with more constraints (e.g., transaction fees, cooldown periods).

Code Solutions

Checking out 5 solutions in different languages for Best Time to Buy and Sell Stock II. Click on different languages to view the code.

public class Solution { public int MaxProfit ( int [] prices ) { int ans = 0 ; for ( int i = 1 ; i < prices . Length ; ++ i ) { ans += Math . Max ( 0 , prices [ i ] - prices [ i - 1 ]); } return ans ; } }

Video Solution

Watch the video walkthrough for Best Time to Buy and Sell Stock II

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

Array

Companies:

Agoda |Deutsche Bank |Goldman Sachs |Infosys |