Log inSign up
mediumLeetCodeNot Started

Best Time to Buy and Sell Stock II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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.

### Example 3 - Input: prices = [7, 6, 4, 3, 1] - Output: 0 - Explanation: No profitable transactions possible.

Constraints:

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the equivalence between multi-state Dynamic Programming and greedy slope accumulation.
  • Formulate standard Hold / Cash stock state machines.
  • Optimize state transitions to O(1) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Unlimited transactions allowed on stock price array.
  • Can hold at most one stock at any time.
  • Maximize cumulative financial return.

Algorithmic Decision Tree:

  • If unlimited transactions -> sum up all ascending slopes or run 2-state DP.
  • If at most K transactions -> expand state to include transaction count.

Connected Patterns:

Best Time to Buy and Sell Stock with CooldownBest Time to Buy and Sell Stock with Transaction Fee

1. Recursive State Exploration

Intuition

At each day, decide whether to buy, sell (if holding), or do nothing. Recurse over all valid states.

Algorithm

  1. Define solve(day, holding).
  2. If day == prices.length, return 0.
  3. If holding: choice 1 is sell prices[day] + solve(day + 1, false), choice 2 is hold solve(day + 1, true).
  4. If not holding: choice 1 is buy -prices[day] + solve(day + 1, true), choice 2 is skip solve(day + 1, false).
  5. Return max of choices.

Recursive Decision Tree All Buy/Sell Schedules

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Lowest initial purchase
Visual state
Values and pointers at this exact step
pointers
S
7
1
5
3
6
4
0
1
↑ buy
2
3
4
5
Variables at this step
boughtAt
1
day
1
Check / comparison
Branch: Buy at Day 1 (price 1)
Decision / next transition
Stock held at cost 1.
Why this step matters

Lowest initial purchase.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int solveRec(int day, bool holding, const vector<int>& prices) {
8 if (day == (int)prices.size()) return 0;
9 if (holding) {
10 int sell = prices[day] + solveRec(day + 1, false, prices);
11 int keep = solveRec(day + 1, true, prices);
12 return max(sell, keep);
13 } else {
14 int buy = -prices[day] + solveRec(day + 1, true, prices);
15 int skip = solveRec(day + 1, false, prices);
16 return max(buy, skip);
17 }
18}
19
20int maxProfitRecursive(const vector<int>& prices) {
21 return solveRec(0, false, prices);
22}
23
24int main() {
25 vector<int> prices = {7, 1, 5, 3, 6, 4};
26 cout << "Max Profit (Recursive): " << maxProfitRecursive(prices) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) recursion stack

2. 2-State Dynamic Programming

Intuition

Maintain two DP states at each day: hold (max profit holding a stock) and cash (max profit with no stock).

Algorithm

  1. Initialize hold = -prices[0], cash = 0.
  2. For i from 1 to prices.length - 1:
  3. newHold = max(hold, cash - prices[i])
  4. newCash = max(cash, hold + prices[i])
  5. hold = newHold, cash = newCash.
  6. Return cash.

Peak-Valley Identification

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Local minimum located
Visual state
Values and pointers at this exact step
pointers
S
7
1
5
3
6
4
0
1
↑ valley 1
2
3
4
5
Variables at this step
valley1
1
Check / comparison
Locate valley 1: price drops from 7 to 1, then rises to 5
Decision / next transition
valley1 = 1 at index 1.
Why this step matters

Local minimum located.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxProfitDP(const vector<int>& prices) {
8 if (prices.empty()) return 0;
9 int hold = -prices[0];
10 int cash = 0;
11
12 for (size_t i = 1; i < prices.size(); i++) {
13 int nextHold = max(hold, cash - prices[i]);
14 int nextCash = max(cash, hold + prices[i]);
15 hold = nextHold;
16 cash = nextCash;
17 }
18 return cash;
19}
20
21int main() {
22 vector<int> prices = {7, 1, 5, 3, 6, 4};
23 cout << "Max Profit (2-State DP): " << maxProfitDP(prices) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) space

3. Greedy One-Pass Slope Accumulation

Intuition

Collect every positive price increment: whenever prices[i] > prices[i-1], add prices[i] - prices[i-1] to profit.

Algorithm

  1. Initialize profit = 0.
  2. For i = 1 to prices.length - 1:
  3. If prices[i] > prices[i - 1]:
  4. profit += prices[i] - prices[i - 1].
  5. Return profit.

Greedy Adjacent Positive Diffs

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Skip negative delta
Visual state
Values and pointers at this exact step
pointers
S
7
1
5
3
6
4
0
↑ i-1
1
↑ i
2
3
4
5
Variables at this step
i
1
profit
0
Check / comparison
i = 1: prices[1]=1 < prices[0]=7 (drop of 6)
Decision / next transition
No profit made on price drops. profit = 0.
Why this step matters

Skip negative delta.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int maxProfitOptimal(const vector<int>& prices) {
7 int profit = 0;
8 for (size_t i = 1; i < prices.size(); i++) {
9 if (prices[i] > prices[i - 1]) {
10 profit += prices[i] - prices[i - 1];
11 }
12 }
13 return profit;
14}
15
16int main() {
17 vector<int> prices = {7, 1, 5, 3, 6, 4};
18 cout << "Max Profit (Optimal Greedy): " << maxProfitOptimal(prices) << endl;
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive SearchO(2^n)O(n)Exhaustive binary choices across all days.Redundant states
2.2-State DP (Hold / Cash)O(n)O(1)State machine tracking best cash with or without stock.None
3.Greedy Slope SumOptimalO(n)O(1)Sum every prices[i] - prices[i-1] > 0.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Assuming we can only buy once: That is Stock I (LeetCode 121), not Stock II.

Pitfall 2:

Trying to find global min and global max: Missing out on multiple intermediate profits.

Crucial Edge Cases to Validate:

  • Prices strictly decreasing: Output is 0.
  • Prices strictly increasing: Output is prices[last] - prices[0].
  • Single day: Output is 0 as no transaction can be completed.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the greedy telescoping logic, then explain the 2-state DP formulation because the DP approach is what enables solving Stock with Cooldown and Stock with Transaction Fee.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does summing all upward adjacent differences (prices[i] - prices[i-1] > 0) achieve the exact optimal profit as buying at the lowest valley and selling at the highest peak?

Back to DSA Sheet