Best Time to Buy and Sell Stock II

🎯

Best Time to Buy and Sell Stock II

mediumGREEDYAmazonFacebookGoogle

Imagine you are a stock trader who can buy and sell stocks multiple times to maximize profit. How do you decide when to buy and sell to get the best total profit?

💡 This problem is about maximizing profit by making multiple buy-sell transactions. Beginners often struggle because they try to find a single best buy-sell pair instead of summing all profitable opportunities. Understanding the greedy approach helps simplify the problem.

📋

Problem Statement

Given an array prices where prices[i] is the price of a given stock on the i-th day, find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). However, you must sell the stock before you buy again. Return the maximum profit you can achieve.

1 ≤ prices.length ≤ 10^50 ≤ prices[i] ≤ 10^4

💡

Example

Input"[7,1,5,3,6,4]"

Output7

Buy on day 2 (price=1), sell on day 3 (price=5), profit=4. Then buy on day 4 (price=3), sell on day 5 (price=6), profit=3. Total profit = 4 + 3 = 7.

Input"[1,2,3,4,5]"

Output4

Buy on day 1 (price=1), sell on day 5 (price=5), profit=4. Continuous increase means buying at start and selling at end is optimal.

Input"[7,6,4,3,1]"

Output0

Prices decrease every day, so no profitable transactions can be made.

• Single day prices [5] → 0 profit because no transactions possible
• All prices equal [3,3,3,3] → 0 profit because no profitable transactions
• Prices with multiple equal peaks [1,2,2,2,3] → profit should count all increases
• Large input with alternating ups and downs [1,2,1,2,1,2] → profit sums all positive diffs

⚠️

Common Mistakes

Trying to find a single best buy-sell pair instead of summing all positive differences

Returns less profit than possible

✅ Sum all positive price differences instead of only one transaction

Adding negative differences or zero differences to profit

Profit decreases or stays same incorrectly

✅ Only add differences when prices[i] > prices[i-1]

Off-by-one errors in loops causing index out of range or missing last day

Runtime errors or incorrect profit calculation

✅ Use correct loop boundaries and conditions

Not handling edge cases like single day or constant prices

Incorrect profit or runtime errors

✅ Add checks or handle these cases explicitly

🧠

Brute Force (Try All Buy-Sell Pairs)

💡 This approach exists to understand the problem deeply by exploring all possible transactions. It is inefficient but helps grasp the problem's combinatorial nature.

Intuition

Try every possible pair of buy and sell days and sum profits of all valid transactions to find the maximum total profit.

Algorithm

1. For each day i, consider buying the stock.
2. For each day j > i, consider selling the stock.
3. Calculate profit if prices[j] > prices[i].
4. Recursively explore all sequences of transactions to find the maximum total profit.

💡 This algorithm is hard because it tries all combinations, leading to exponential complexity and overlapping subproblems.

</>

Code

def maxProfit(prices):
    def dfs(i):
        if i >= len(prices):
            return 0
        max_profit = 0
        for j in range(i+1, len(prices)):
            if prices[j] > prices[i]:
                profit = prices[j] - prices[i] + dfs(j+1)
                max_profit = max(max_profit, profit)
        skip = dfs(i+1)
        return max(max_profit, skip)

# Driver code
if __name__ == '__main__':
    prices = [7,1,5,3,6,4]
    print(maxProfit(prices))

Line Notes

def dfs(i):Defines recursive helper to explore transactions starting at day i

if i >= len(prices):Base case: no more days left to trade

for j in range(i+1, len(prices))Try selling on every day after buying day i

if prices[j] > prices[i]:Only consider profitable transactions

profit = prices[j] - prices[i] + dfs(j+1)Profit from current transaction plus future profits

skip = dfs(i+1)Option to skip buying on day i

return max(max_profit, skip)Choose the best between buying or skipping

public class Solution {
    public int maxProfit(int[] prices) {
        return dfs(prices, 0);
    }
    private int dfs(int[] prices, int i) {
        if (i >= prices.length) return 0;
        int maxProfit = 0;
        for (int j = i + 1; j < prices.length; j++) {
            if (prices[j] > prices[i]) {
                int profit = prices[j] - prices[i] + dfs(prices, j + 1);
                maxProfit = Math.max(maxProfit, profit);
            }
        }
        int skip = dfs(prices, i + 1);
        return Math.max(maxProfit, skip);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] prices = {7,1,5,3,6,4};
        System.out.println(sol.maxProfit(prices));
    }
}

Line Notes

public int maxProfit(int[] prices)Entry point for the solution

return dfs(prices, 0);Start recursion from day 0

if (i >= prices.length) return 0;Base case: no more days to trade

for (int j = i + 1; j < prices.length; j++)Try all sell days after buy day i

if (prices[j] > prices[i])Only consider profitable transactions

int profit = prices[j] - prices[i] + dfs(prices, j + 1);Profit plus future profits

int skip = dfs(prices, i + 1);Option to skip buying on day i

return Math.max(maxProfit, skip);Choose best option

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int dfs(const vector<int>& prices, int i) {
        if (i >= prices.size()) return 0;
        int maxProfit = 0;
        for (int j = i + 1; j < prices.size(); ++j) {
            if (prices[j] > prices[i]) {
                int profit = prices[j] - prices[i] + dfs(prices, j + 1);
                maxProfit = max(maxProfit, profit);
            }
        }
        int skip = dfs(prices, i + 1);
        return max(maxProfit, skip);
    }
    int maxProfit(vector<int>& prices) {
        return dfs(prices, 0);
    }
};

int main() {
    Solution sol;
    vector<int> prices = {7,1,5,3,6,4};
    cout << sol.maxProfit(prices) << endl;
    return 0;
}

Line Notes

int dfs(const vector<int>& prices, int i)Recursive helper exploring transactions from day i

if (i >= prices.size()) return 0;Base case: no more days to trade

for (int j = i + 1; j < prices.size(); ++j)Try all sell days after buy day i

if (prices[j] > prices[i])Only consider profitable transactions

int profit = prices[j] - prices[i] + dfs(prices, j + 1);Profit plus future profits

int skip = dfs(prices, i + 1);Option to skip buying on day i

return max(maxProfit, skip);Choose best option

function maxProfit(prices) {
    function dfs(i) {
        if (i >= prices.length) return 0;
        let maxProfit = 0;
        for (let j = i + 1; j < prices.length; j++) {
            if (prices[j] > prices[i]) {
                let profit = prices[j] - prices[i] + dfs(j + 1);
                maxProfit = Math.max(maxProfit, profit);
            }
        }
        let skip = dfs(i + 1);
        return Math.max(maxProfit, skip);
    }
    return dfs(0);
}

// Test
console.log(maxProfit([7,1,5,3,6,4]));

Line Notes

function dfs(i)Recursive helper to explore transactions from day i

if (i >= prices.length) return 0;Base case: no more days to trade

for (let j = i + 1; j < prices.length; j++)Try all sell days after buy day i

if (prices[j] > prices[i])Only consider profitable transactions

let profit = prices[j] - prices[i] + dfs(j + 1);Profit plus future profits

let skip = dfs(i + 1);Option to skip buying on day i

return Math.max(maxProfit, skip);Choose best option

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

For each day, we decide to buy or skip, leading to exponential branching.

💡 For n=20, this means over a million recursive calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and motivates optimization.

🧠

Greedy Approach (Sum All Positive Differences)

💡 This approach exists because the problem allows unlimited transactions, so summing all positive price differences yields the maximum profit efficiently.

Intuition

Every time the price goes up from one day to the next, we can profit by buying the previous day and selling the next day. Summing all these positive gains gives the maximum profit.

Algorithm

1. Initialize total profit to 0.
2. Iterate through prices from day 1 to end.
3. If price on day i is greater than day i-1, add the difference to total profit.
4. Return total profit after iteration.

💡 This algorithm is straightforward but requires understanding why summing all positive differences works.

</>

Code

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

# Driver code
if __name__ == '__main__':
    prices = [7,1,5,3,6,4]
    print(maxProfit(prices))

Line Notes

profit = 0Initialize profit accumulator

for i in range(1, len(prices))Iterate over days starting from second day

if prices[i] > prices[i - 1]Check if price increased from previous day

profit += prices[i] - prices[i - 1]Add positive difference to profit

return profitReturn total accumulated profit

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] prices = {7,1,5,3,6,4};
        System.out.println(sol.maxProfit(prices));
    }
}

Line Notes

int profit = 0;Initialize profit accumulator

for (int i = 1; i < prices.length; i++)Iterate from second day to last

if (prices[i] > prices[i - 1])Check for price increase

profit += prices[i] - prices[i - 1];Add positive difference to profit

return profit;Return total profit

#include <iostream>
#include <vector>
using namespace std;

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

int main() {
    Solution sol;
    vector<int> prices = {7,1,5,3,6,4};
    cout << sol.maxProfit(prices) << endl;
    return 0;
}

Line Notes

int profit = 0;Initialize profit accumulator

for (int i = 1; i < prices.size(); ++i)Iterate from second day to last

if (prices[i] > prices[i - 1])Check for price increase

profit += prices[i] - prices[i - 1];Add positive difference to profit

return profit;Return total profit

function maxProfit(prices) {
    let profit = 0;
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}

// Test
console.log(maxProfit([7,1,5,3,6,4]));

Line Notes

let profit = 0;Initialize profit accumulator

for (let i = 1; i < prices.length; i++)Iterate from second day to last

if (prices[i] > prices[i - 1])Check for price increase

profit += prices[i] - prices[i - 1];Add positive difference to profit

return profit;Return total profit

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through prices array, constant extra space.

💡 For n=100,000, this means 100,000 operations, which is efficient for interviews.

Interview Verdict: Accepted

This is the optimal and accepted solution for this problem.

🧠

Peak-Valley Approach (Greedy Variant)

💡 This approach explicitly finds valleys (local minima) to buy and peaks (local maxima) to sell, reinforcing the greedy intuition.

Intuition

Buy at every local minimum and sell at the next local maximum to capture all profitable segments.

Algorithm

1. Initialize total profit to 0 and start index at 0.
2. While not at the end, find next valley (lowest price).
3. Then find next peak (highest price after valley).
4. Add peak - valley to total profit and repeat until end.

💡 This approach is more explicit and intuitive but equivalent to summing positive differences.

</>

Code

def maxProfit(prices):
    i = 0
    profit = 0
    n = len(prices)
    while i < n - 1:
        while i < n - 1 and prices[i] >= prices[i + 1]:
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i] <= prices[i + 1]:
            i += 1
        peak = prices[i]
        profit += peak - valley
    return profit

# Driver code
if __name__ == '__main__':
    prices = [7,1,5,3,6,4]
    print(maxProfit(prices))

Line Notes

i = 0Initialize index to start of array

while i < n - 1 and prices[i] >= prices[i + 1]Find next valley by skipping descending prices

valley = prices[i]Record valley price to buy

while i < n - 1 and prices[i] <= prices[i + 1]Find next peak by skipping ascending prices

peak = prices[i]Record peak price to sell

profit += peak - valleyAdd profit from valley to peak transaction

public class Solution {
    public int maxProfit(int[] prices) {
        int i = 0, profit = 0, n = prices.length;
        while (i < n - 1) {
            while (i < n - 1 && prices[i] >= prices[i + 1]) i++;
            int valley = prices[i];
            while (i < n - 1 && prices[i] <= prices[i + 1]) i++;
            int peak = prices[i];
            profit += peak - valley;
        }
        return profit;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] prices = {7,1,5,3,6,4};
        System.out.println(sol.maxProfit(prices));
    }
}

Line Notes

int i = 0, profit = 0, n = prices.length;Initialize index, profit, and array length

while (i < n - 1 && prices[i] >= prices[i + 1]) i++;Find next valley by skipping descending prices

int valley = prices[i];Record valley price to buy

while (i < n - 1 && prices[i] <= prices[i + 1]) i++;Find next peak by skipping ascending prices

int peak = prices[i];Record peak price to sell

profit += peak - valley;Add profit from valley to peak transaction

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0, profit = 0, n = prices.size();
        while (i < n - 1) {
            while (i < n - 1 && prices[i] >= prices[i + 1]) i++;
            int valley = prices[i];
            while (i < n - 1 && prices[i] <= prices[i + 1]) i++;
            int peak = prices[i];
            profit += peak - valley;
        }
        return profit;
    }
};

int main() {
    Solution sol;
    vector<int> prices = {7,1,5,3,6,4};
    cout << sol.maxProfit(prices) << endl;
    return 0;
}

Line Notes

int i = 0, profit = 0, n = prices.size();Initialize index, profit, and array length

while (i < n - 1 && prices[i] >= prices[i + 1]) i++;Find next valley by skipping descending prices

int valley = prices[i];Record valley price to buy

while (i < n - 1 && prices[i] <= prices[i + 1]) i++;Find next peak by skipping ascending prices

int peak = prices[i];Record peak price to sell

profit += peak - valley;Add profit from valley to peak transaction

function maxProfit(prices) {
    let i = 0, profit = 0, n = prices.length;
    while (i < n - 1) {
        while (i < n - 1 && prices[i] >= prices[i + 1]) i++;
        let valley = prices[i];
        while (i < n - 1 && prices[i] <= prices[i + 1]) i++;
        let peak = prices[i];
        profit += peak - valley;
    }
    return profit;
}

// Test
console.log(maxProfit([7,1,5,3,6,4]));

Line Notes

let i = 0, profit = 0, n = prices.length;Initialize index, profit, and array length

while (i < n - 1 && prices[i] >= prices[i + 1]) i++;Find next valley by skipping descending prices

let valley = prices[i];Record valley price to buy

while (i < n - 1 && prices[i] <= prices[i + 1]) i++;Find next peak by skipping ascending prices

let peak = prices[i];Record peak price to sell

profit += peak - valley;Add profit from valley to peak transaction

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass with two inner while loops that together cover the array once.

💡 For large n, this approach is efficient and easy to understand visually.

Interview Verdict: Accepted

This approach is equivalent to the sum of positive differences but more explicit in reasoning.

📊

All Approaches - One-Glance Tradeoffs

💡 The greedy approach (Approach 2) is the best to code in interviews due to its simplicity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Greedy Sum Positive Differences	O(n)	O(1)	No	N/A	Code this approach
3. Peak-Valley Approach	O(n)	O(1)	No	N/A	Explain as alternative to Approach 2

💼

Interview Strategy

💡 Use this guide to understand the problem from brute force to optimal greedy solutions. Practice explaining each approach clearly and test edge cases.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding of the problem.Step 3: Explain why brute force is inefficient and introduce the greedy approach.Step 4: Code the greedy solution and test with examples.Step 5: Discuss edge cases and possible follow-ups.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 7min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force to greedy, and correctness in handling edge cases.

Common Follow-ups

• What if you can only complete at most two transactions? → Use DP approach.
• What if there is a cooldown day after selling? → Modify DP with cooldown states.

💡 These follow-ups test your ability to adapt greedy to DP or add constraints.

🔍

Pattern Recognition

When to Use

1) Problem involves buying and selling stocks multiple times; 2) Unlimited transactions allowed; 3) Maximize total profit; 4) Prices given as array

Signature Phrases

'You may complete as many transactions as you like''Maximize total profit from multiple buy-sell pairs'

NOT This Pattern When

Problems with only one transaction allowed or with transaction fees require different approaches.

Similar Problems

Best Time to Buy and Sell Stock I - single transaction max profitBest Time to Buy and Sell Stock III - at most two transactionsBest Time to Buy and Sell Stock with Cooldown - transactions with cooldown constraint

Practice

1. You have a circular route with gas stations, each providing some gas and requiring some cost to travel to the next station. You want to find a starting station to complete the full circle without running out of gas. Which algorithmic approach guarantees finding the correct starting station efficiently?

easy

A. Divide and conquer by splitting the circle into halves and solving recursively

B. Dynamic Programming to store maximum gas reachable from each station

C. Brute force by simulating the trip starting from each station until success or failure

D. Greedy approach that checks total gas vs total cost and resets start when tank goes negative

Solution

1. Step 1: Understand problem constraints

   The problem requires finding a single start station to complete a circular route without running out of gas, which can be solved efficiently by a greedy approach.

2. Step 2: Identify the correct approach

   The greedy method that first checks if total gas is at least total cost ensures a solution exists, then resets the start whenever the tank goes negative, guaranteeing an O(n) solution.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy reset approach is optimal and widely accepted [OK]

Hint: Check total gas vs cost, then reset start on negative tank [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Using DP which is unnecessary
• Trying divide and conquer which doesn't fit circular nature

2. Given the following code for partitioning labels, what is the returned list when the input string is "eccbbbbdec"?

def partitionLabels(s):
    last = [0] * 26
    for i, c in enumerate(s):
        last[ord(c) - ord('a')] = i
    res = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        end = max(end, last[ord(c) - ord('a')])
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

easy

A. [10]

B. [9, 1]

C. [1, 9]

D. [3, 7]

Solution

1. Step 1: Compute last occurrences

   Characters: e last at 8, c last at 9, b last at 6, d last at 7.

2. Step 2: Trace partitions

   Start=0, end=0 initially. Iterate: - i=0 (e): end=max(0,8)=8 - i=1 (c): end=max(8,9)=9 - i=2 (c): end=9 - i=3 (b): end=max(9,6)=9 - i=4 (b): end=9 - i=5 (b): end=9 - i=6 (b): end=9 - i=7 (d): end=max(9,7)=9 - i=8 (e): end=9 - i=9 (c): i==end, partition size=9-0+1=10 Append 10, start=10 (end of string) But since string length is 10, only one partition of size 10. However, careful: last occurrence of 'e' is 8, 'c' is 9, so partition ends at 9. So only one partition of size 10.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Partition covers entire string length 10 [OK]

Hint: Track max last occurrence to find partition end [OK]

Common Mistakes:

• Miscounting partition size by off-by-one
• Stopping partition too early ignoring max last occurrence
• Confusing character indices

3. Examine the following BFS-based code for Jump Game II. Which line contains a subtle bug that can cause incorrect jump counts or infinite loops?

medium

A. Line checking if next_pos == n - 1 to return jumps

B. Line incrementing jumps before processing current level

C. Line calculating furthest_jump without bounding by n-1

D. Line adding next_pos to visited set

Solution

1. Step 1: Identify furthest_jump calculation

   furthest_jump = pos + nums[pos] can exceed array bounds, causing range() to go out of range or runtime error.

2. Step 2: Check impact

   Without min(pos + nums[pos], n - 1), code may attempt invalid indices, causing incorrect behavior or crashes.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bounding furthest_jump by n-1 prevents out-of-range errors [OK]

Hint: Always bound jump indices within array length [OK]

Common Mistakes:

• Forgetting to limit furthest_jump to n-1
• Incrementing jumps incorrectly
• Missing visited set usage

4. What is the time complexity of the optimal Task Scheduler algorithm using a max-heap for t total tasks and m unique tasks?

medium

A. O(t log m) because each task is pushed and popped from a heap of size up to m

B. O(t + m) because counting frequencies and scheduling are linear

C. O(m log t) because heap operations depend on total tasks

D. O(t * m) because each task may be compared with all unique tasks

Solution

1. Step 1: Analyze heap operations

   Heap size is at most m (unique tasks). Each task is pushed and popped at most once per execution.

2. Step 2: Calculate total operations

   For t tasks, each heap operation costs O(log m), so total is O(t log m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size depends on unique tasks, not total tasks [OK]

Hint: Heap operations scale with unique tasks, not total tasks [OK]

Common Mistakes:

• Confusing total tasks and unique tasks
• Assuming linear heap operations
• Ignoring log factor in heap push/pop

5. Suppose now each cookie can be assigned to multiple children (reusable cookies). Which modification to the original greedy algorithm correctly computes the maximum number of content children?

hard

A. Sort both arrays and increment both pointers i and j on assignment as before

B. Use the brute force nested loops approach to try all assignments since greedy fails with reusable cookies

C. Sort greed array only and assign the largest cookie to each child without sorting cookies

D. Keep sorting arrays, but do not increment cookie pointer j when a cookie is assigned; only increment child pointer i

Solution

1. Step 1: Understand reuse effect

   Cookies can be assigned multiple times, so cookie pointer j should not advance on assignment.

2. Step 2: Modify greedy accordingly

   Keep sorting both arrays, but only increment child pointer i when a cookie satisfies a child; j stays to reuse the same cookie.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Not incrementing j allows cookie reuse [OK]

Hint: Do not advance cookie pointer on assignment for reuse [OK]

Common Mistakes:

• Incrementing both pointers breaks reuse
• Using brute force unnecessarily
• Ignoring sorting leads to suboptimal matches