Skip to main content
Talentd

Best Time to Buy and Sell Stock II - Solution & Explanation

MediumArrayDynamic ProgrammingGreedy24 min readAsked at: Amazon, Microsoft, Apple +25
Practice this problem

Problem Statement

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:

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 * 104
  • 0 <= prices[i] <= 104

Approach Overview

Problem Overview: You are given an array where prices[i] represents the stock price on day i. You can buy and sell the stock multiple times, but you cannot hold more than one share at a time. The goal is to compute the maximum profit you can achieve by choosing optimal buy and sell days.

This problem is fundamentally about capturing every profitable upward price movement. Instead of searching for a single global maximum transaction, you accumulate profit across multiple smaller trades. The structure of the array and the ability to perform unlimited transactions makes Greedy strategies particularly effective.

Approach 1: Peak-Valley Approach (O(n) time, O(1) space)

This approach explicitly identifies local valleys (buy points) and local peaks (sell points). Iterate through the array while skipping descending prices until you find a valley. Once a valley is found, continue scanning forward until the prices stop increasing, which marks the peak. The profit for that segment is peak - valley. Add it to the total profit and continue scanning the remaining array.

The key insight is that every increasing sequence can be treated as a profitable transaction. Instead of computing all pairs, the algorithm captures profit from each upward segment. This approach mirrors how traders reason about trends and makes the transaction boundaries explicit. Time complexity is O(n) since each element is visited at most once, and space complexity is O(1).

Approach 2: Simple One-Pass Greedy (O(n) time, O(1) space)

The peak-valley logic can be simplified further. Any time prices[i] > prices[i-1], you add the difference prices[i] - prices[i-1] to the profit. This effectively captures the profit of every upward step. Multiple consecutive increases naturally accumulate into the same total profit as buying at the valley and selling at the peak.

The insight is that (peak - valley) equals the sum of all incremental increases between them. For example, if prices go from 1 → 3 → 5, the profit (5-1) equals (3-1) + (5-3). By adding positive differences during a single pass, the algorithm automatically collects the optimal profit without explicitly detecting valleys or peaks.

This greedy strategy is the cleanest implementation and the one most commonly expected in interviews. It runs in O(n) time with O(1) space and requires only a single loop over the array.

Although the reasoning can also be framed using Dynamic Programming (tracking hold vs. not-hold states), the DP transitions simplify directly into the greedy rule above when unlimited transactions are allowed.

Recommended for interviews: The one-pass greedy solution is the expected answer. It demonstrates that you recognize the additive property of incremental price increases and can reduce the problem to a single linear scan. Mentioning the peak-valley reasoning first helps explain why the greedy rule works, then implementing the one-pass version shows strong optimization skills.

Approach 1: Peak-Valley Approach

The Peak-Valley Approach aims to identify opportunities where a buy (at a valley) and a sell (at a peak) transaction yields profit. The idea is to take advantage of every upward trend between valleys and peaks and sum up the differences.

The code iterates over the price array. Whenever a profit opportunity is identified (when today's price is higher than yesterday's), the difference is added to the total profit. This maximizes profit by summing up all 'up-hill' gains directly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of prices.
Space Complexity: O(1), no additional space is used.

Try this approach in the editor →

Approach 2: Simple One-Pass Greedy Approach

The simple one-pass greedy approach makes a decision on each day based on whether the price will go up (buy or hold) or down (sell or do nothing). This maximizes profit by keeping solutions simple, efficient and using the greedy approach to sum up all local gains.

This solution follows a greedy logic where each upward opportunity is utilized. For each day, if the current day's price is greater than the previous day's, the difference is added to the profit.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 3: Greedy Algorithm

Starting from the second day, if the stock price is higher than the previous day, buy on the previous day and sell on the current day to make a profit. If the stock price is lower than the previous day, do not buy or sell. In other words, buy and sell on all rising trading days, and do not trade on all falling trading days. The final profit will be the maximum.

The time complexity is O(n), where n is the length of the prices array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Approach 4: Dynamic Programming

We define f[i][j] as the maximum profit after trading on the ith day, where j indicates whether we currently hold the stock. When holding the stock, j=0, and when not holding the stock, j=1. The initial state is f[0][0]=-prices[0], and all other states are 0.

If we currently hold the stock, it may be that we held the stock the day before and do nothing today, i.e., f[i][0]=f[i-1][0]. Or it may be that we did not hold the stock the day before and bought the stock today, i.e., f[i][0]=f[i-1][1]-prices[i].

If we currently do not hold the stock, it may be that we did not hold the stock the day before and do nothing today, i.e., f[i][1]=f[i-1][1]. Or it may be that we held the stock the day before and sold the stock today, i.e., f[i][1]=f[i-1][0]+prices[i].

Therefore, we can write the state transition equation as:

$ \begin{cases} f[i][0]=max(f[i-1][0],f[i-1][1]-prices[i])\ f[i][1]=max(f[i-1][1],f[i-1][0]+prices[i]) \end{cases}

The final answer is f[n-1][1], where n is the length of the prices array.

The time complexity is O(n), and the space complexity is O(n). Here, n$ is the length of the prices array.

Code

PythonJavaC++GoC#

Python

Java

C++

Go

C#

Try this approach in the editor →

Approach 5: Dynamic Programming (Space Optimization)

We can find that in Solution 2, the state of the ith day is only related to the state of the i-1th day. Therefore, we can use only two variables to maintain the state of the i-1th day, thereby optimizing the space complexity to O(1).

The time complexity is O(n), where n is the length of the prices array. The space complexity is O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Peak-Valley Approach

Time Complexity: O(n), where n is the number of prices.
Space Complexity: O(1), no additional space is used.

Simple One-Pass Greedy Approach

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

Greedy Algorithm—
Dynamic Programming—
Dynamic Programming (Space Optimization)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Peak-Valley ApproachO(n)O(1)Useful when you want explicit buy/sell boundaries and clearer reasoning about trading segments.
One-Pass Greedy (Sum of Positive Differences)O(n)O(1)Best for interviews and production code due to its minimal logic and single-pass implementation.

Video Solution

DP 36. Buy and Sell Stock - II | Recursion to Space Optimisation • take U forward • 446,905 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Best Time to Buy and Sell Stock II easy or hard?
Best Time to Buy and Sell Stock II is generally considered a medium difficulty problem. The implementation is short, but recognizing that every increasing price difference can be added greedily requires algorithmic insight.
Best Time to Buy and Sell Stock II Python/Java solution
The typical Python or Java implementation uses a single loop through the prices array and accumulates positive differences between consecutive elements. This greedy approach produces the maximum profit in O(n) time and O(1) space.
How to solve Best Time to Buy and Sell Stock II in O(n)?
Traverse the array once and accumulate profit whenever the price increases from the previous day. If prices[i] > prices[i-1], add prices[i] - prices[i-1] to the total profit. This greedy rule captures all profitable segments without explicitly finding valleys and peaks.
What is the best approach for Best Time to Buy and Sell Stock II?
The best approach is the greedy one-pass method. Iterate through the price array and add every positive difference between consecutive days (prices[i] - prices[i-1]). This captures all profitable upward movements. The algorithm runs in O(n) time with O(1) extra space.
Is Best Time to Buy and Sell Stock II asked at Google/Amazon/Meta?
Best Time to Buy and Sell Stock II is a classic interview problem frequently asked at large tech companies including Amazon, Google, Meta, and Microsoft. It tests understanding of greedy algorithms and the ability to simplify dynamic programming state transitions.
What data structure is used in Best Time to Buy and Sell Stock II?
The problem primarily uses an array to represent daily stock prices. The algorithm operates directly on the array using simple iteration, without requiring additional data structures beyond a few variables for tracking profit.
What is the time complexity of Best Time to Buy and Sell Stock II?
The optimal solution runs in O(n) time because the algorithm scans the price array once. Each element is compared with its previous value to detect profitable increases. Space complexity remains O(1) since only a few variables are used to track profit.

Ready to solve this problem?

Practice Best Time to Buy and Sell Stock II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Best Time to Buy and Sell Stock

Next

Best Time to Buy and Sell Stock III