Subramanya's Digital Garden

Recent Notes

122. Best Time to Buy and Sell Stock II

9 min read

Solving “Best Time to Buy and Sell Stock II”

In this problem, we’re tasked with finding the maximum profit we can make from buying and selling a stock. The key difference from the classic “buy once, sell once” problem is that here we can transact as many times as we want. The only constraint is that we must sell a stock before we can buy another one.

Let’s break down how to approach this problem with a simple, greedy strategy.

Intuition

My first thought when looking at this problem is that we want to capitalize on every opportunity to make a profit. Since we can buy and sell multiple times, any time the stock price goes up, we should be able to gain from it.

Imagine a stock price chart. The price fluctuates daily. A profitable transaction is simply buying at a low point (a “valley”) and selling at a subsequent high point (a “peak”).

Since we can perform as many transactions as needed, we don’t have to worry about finding the absolute lowest valley and the absolute highest peak. We can simply capture all the smaller, incremental profits. For example, if the price goes up from day 1 to day 2, and then again from day 2 to day 3, we can think of this in two ways:

  1. Buy on day 1, sell on day 3.
  2. Buy on day 1, sell on day 2. Then, buy on day 2, sell on day 3.

Mathematically, the profit is the same in both cases. If prices are p_1, p_2, p_3, the profit for case 1 is p_3−p_1. For case 2, the total profit is (p_2−p_1)+(p_3−p_2), which simplifies to p_3−p_1.

This insight simplifies the problem immensely. We can just add up all the profits from every single day-to-day price increase. This greedy approach works because we are essentially collecting the profit from every upward trend in the stock’s price, no matter how small.

Approach

The strategy is straightforward: iterate through the stock prices and accumulate profit whenever the price on the current day is higher than the price on the previous day.

Here is the step-by-step breakdown:

  1. Initialize a variable, let’s call it totalProfit, to zero. This variable will keep track of our accumulated gains.
  2. Loop through the prices array, starting from the second day (index 1). We start at the second day because we need to compare it with the previous day.
  3. Inside the loop, for each day i, check if the price on this day, prices[i], is greater than the price on the previous day, prices[i-1].
  4. If prices[i] > prices[i-1], it represents a profitable opportunity. Calculate the profit for this small transaction: prices[i] - prices[i-1].
  5. Add this profit to our totalProfit.
  6. Continue this process until you have checked all the days.
  7. After the loop finishes, totalProfit will hold the maximum possible profit.

This method ensures we capture every single bit of profit available from the price movements.

Complexity

  • Time complexity:

    O(n)

    We iterate through the prices array of length n just once. Therefore, the time taken is directly proportional to the number of days, giving us a linear time complexity.

  • Space complexity:

    O(1)

    Our solution only requires a single extra variable (totalProfit) to store the cumulative profit. The amount of memory used does not increase with the size of the input array, so the space complexity is constant.

Code

Here are the implementations of this approach in C++, Java, Python, and JavaScript.

C++

C++

#include <vector>

class Solution {
public:
    /**
     * @brief Calculates the maximum profit that can be obtained.
     * @param prices A vector of integers representing the stock prices on consecutive days.
     * @return The maximum profit.
     */
    int maxProfit(std::vector<int>& prices) {
        int totalProfit = 0;
        // Start from the second day (index 1) to compare with the previous day
        for (int i = 1; i < prices.size(); i++) {
            // If the price today is higher than yesterday, we can make a profit
            if (prices[i] > prices[i-1]) {
                // Add the profit from this transaction to the total
                totalProfit += prices[i] - prices[i-1];
            }
        }
        return totalProfit;
    }
};

Java

Java

class Solution {
    /**
     * Calculates the maximum profit that can be obtained.
     * @param prices An array of integers representing the stock prices on consecutive days.
     * @return The maximum profit.
     */
    public int maxProfit(int[] prices) {
        int totalProfit = 0;
        // Start from the second day (index 1) to compare with the previous day
        for (int i = 1; i < prices.length; i++) {
            // If the price today is higher than yesterday, we can make a profit
            if (prices[i] > prices[i - 1]) {
                // Add the profit from this transaction to the total
                totalProfit += prices[i] - prices[i - 1];
            }
        }
        return totalProfit;
    }
}

Python

Python

from typing import List

class Solution:
    """
    Calculates the maximum profit that can be obtained.
    """
    def maxProfit(self, prices: List[int]) -> int:
        """
        :param prices: A list of integers representing the stock prices on consecutive days.
        :return: The maximum profit.
        """
        total_profit = 0
        # Start from the second day (index 1) to compare with the previous day
        for i in range(1, len(prices)):
            # If the price today is higher than yesterday, we can make a profit
            if prices[i] > prices[i-1]:
                # Add the profit from this transaction to the total
                total_profit += prices[i] - prices[i-1]
        return total_profit

JavaScript

JavaScript

/**
 * Calculates the maximum profit that can be obtained.
 * @param {number[]} prices An array of integers representing the stock prices on consecutive days.
 * @return {number} The maximum profit.
 */
var maxProfit = function(prices) {
    let totalProfit = 0;
    // Start from the second day (index 1) to compare with the previous day
    for (let i = 1; i < prices.length; i++) {
        // If the price today is higher than yesterday, we can make a profit
        if (prices[i] > prices[i - 1]) {
            // Add the profit from this transaction to the total
            totalProfit += prices[i] - prices[i - 1];
        }
    }
    return totalProfit;
};

How to Recognize Similar Problems

The approach we used is a classic Greedy Algorithm. Greedy algorithms work by making the locally optimal choice at each step with the hope of finding a global optimum. Here are the key signals to look for in a problem that might be solvable with a similar greedy strategy:

  1. Maximization/Minimization Goal: The problem will often ask you to find the “maximum” profit, “minimum” cost, “largest” number, or “least” number of operations. This is a common characteristic of optimization problems where greedy strategies can be effective.
  2. Possibility of Local Choices: Look at the problem and ask yourself: “Can I make a simple choice right now, based on my immediate situation, that seems like the best move?” In our stock problem, the choice was: “If the price went up since yesterday, I’ll take that profit.”
  3. Independent Decisions: The most crucial factor for a greedy algorithm is that a local choice must not negatively impact future optimal choices. In our problem, selling the stock today to take a small profit doesn’t prevent us from buying it back tomorrow if another opportunity arises. The decisions are independent.
    • Contrast this with a problem where a greedy choice fails: In the “Best Time to Buy and Sell Stock I” (where you can only transact once), you can’t just sell on the first day the price goes up. A small profit now might prevent you from getting a much larger profit later. This is a sign that a simple greedy approach won’t work, and you might need another technique like Dynamic Programming.
  4. Cumulative Result: The final answer is often a sum or an accumulation of the results of these local choices. We built our totalProfit by adding up lots of small, daily profits. If the problem can be broken down into pieces, and the final answer is the sum of the solutions to the pieces, it’s a good candidate.

Example Problems with a Similar Greedy Pattern:

  • Assign Cookies (LeetCode 455): You have cookies of different sizes and children with different greed factors. To maximize the number of content children, you greedily give the smallest cookie that can satisfy the least greedy child.
  • Gas Station (LeetCode 134): To find if you can complete a circuit, you greedily move from one station to the next, as long as you have enough gas. The logic involves checking if the cumulative gas - cost remains non-negative.
  • Jump Game (LeetCode 55): To see if you can reach the last index, at each step you make a greedy choice to jump to the position that extends your reach the farthest.

How to Remember the Concept

Memorizing code is fragile; understanding the core idea is robust. Here are some techniques to internalize a problem-solving pattern:

  1. Name the Pattern: Give the technique a name. We can call this one the “Cumulative Gains” or “Valley-Peak” approach. By labeling it, you create a mental hook that’s easier to recall than the code itself. You can say, “Oh, this looks like a cumulative gains problem,” and that will trigger the memory of the logic.
  2. Focus on the “Aha!” Moment: What was the key insight that made the problem simple? For this problem, it was the realization that the profit from a long upward trend (e.g., prices 1, 5) is equal to the sum of the profits from the smaller day-to-day increases within that trend (5 - 1 = (2-1) + (3-2) + (4-3) + (5-4)). Cement this core logic in your mind. If you remember why it works, you can reconstruct the code anytime.
  3. Practice with Variations: The best way to master a concept is to see it in different contexts. The “Best Time to Buy and Sell Stock” series on LeetCode is perfect for this:
    • Stock I: Only one transaction allowed. (Helps you see the limits of our greedy approach).
    • Stock III/IV: At most 2 or k transactions. (Requires a more advanced technique, forcing you to understand when greedy isn’t enough).
    • Stock with Cooldown/Transaction Fee: Adds new constraints that modify the original greedy logic. By tackling these related problems, you’ll develop a much deeper and more flexible understanding of the pattern.
  4. Spaced Repetition: Don’t just solve it and forget it. After a week, try to solve the problem again from scratch without looking at your old code. Then try again in a month. This practice strengthens the neural pathways and moves the concept into your long-term memory.
  5. Explain It to Someone Else: Try to explain the solution and the logic to a friend, or write it down in your own words. The process of teaching forces you to clarify your own understanding and expose any gaps in your knowledge.

Graph View