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 list of children each with a greed factor and a list of cookies each with a size. You want to assign cookies to children so that each child gets at most one cookie and the cookie size is at least the child's greed factor. Which algorithmic approach guarantees the maximum number of content children?

easy

A. Greedy algorithm by sorting greed factors and cookie sizes, then assigning smallest sufficient cookie to each child

B. Dynamic Programming to try all possible assignments and pick the best

C. Brute force nested loops checking every cookie for every child without sorting

D. Divide and Conquer by splitting children and cookies and merging results

Solution

1. Step 1: Understand problem constraints

   Each child can get at most one cookie, and the cookie must satisfy the child's greed factor.

2. Step 2: Identify optimal approach

   Sorting both greed and cookie arrays allows a greedy assignment from smallest greed to smallest sufficient cookie, ensuring maximum matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy sorting approach is classic for assignment problems [OK]

Hint: Sort both arrays and assign greedily [OK]

Common Mistakes:

• Thinking brute force is needed for optimality
• Assuming DP is required
• Ignoring sorting leads to suboptimal matches

2. 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

3. Given the following code and input, what is the final returned total cost?

def twoCitySchedCost(costs):
    costs.sort(key=lambda x: x[0] - x[1])
    n = len(costs) // 2
    total = 0
    for i, cost in enumerate(costs):
        if i < n:
            total += cost[0]
        else:
            total += cost[1]
    return total

costs = [[10,20],[30,200],[400,50],[30,20]]
print(twoCitySchedCost(costs))

easy

A. 110

B. 150

C. 120

D. 140

Solution

1. Step 1: Sort costs by difference cost[0] - cost[1]

   Differences: [10-20=-10, 30-200=-170, 400-50=350, 30-20=10]. Sorted: [[30,200], [10,20], [30,20], [400,50]]

2. Step 2: Assign first half to city A, rest to city B and sum costs

   First two: city A costs = 30 + 10 = 40; last two: city B costs = 20 + 50 = 70; total = 40 + 70 = 110

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum matches manual calculation [OK]

Hint: Sort by difference, assign first half to city A [OK]

Common Mistakes:

• Misordering after sorting by difference
• Off-by-one in loop boundary
• Adding wrong city cost for last half

4. What is the time complexity of the optimal two-pass greedy candy distribution algorithm for an input array of length n?

medium

A. O(n) because each pass scans the array once

B. O(n^2) due to nested loops in adjustment

C. O(n log n) due to sorting or priority queue usage

D. O(n) but with O(n) auxiliary space for candies array

Solution

1. Step 1: Identify loops in the algorithm

   Two separate passes over the array, each iterating from start to end or end to start once.

2. Step 2: Analyze complexity of each pass

   Each pass is O(n), no nested loops or sorting involved, so total time is O(n). Also, the candies array requires O(n) auxiliary space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two linear scans and O(n) space for candies array [OK]

Hint: Two linear passes -> O(n) time and O(n) space [OK]

Common Mistakes:

• Confusing repeated adjustment brute force with optimal approach
• Assuming sorting is needed
• Ignoring that passes are sequential, not nested

5. What is the time complexity of the optimal greedy algorithm for the wiggle subsequence problem, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because it scans the list once, updating counters based on difference signs

B. O(2^n) because it explores all subsequences recursively

C. O(n log n) due to sorting or binary search steps involved

D. O(n^2) because it compares each element with all previous elements

Solution

1. Step 1: Analyze algorithm operations

   The greedy algorithm iterates through the list once, computing differences and updating counters in O(1) time per element.

2. Step 2: Address common misconceptions

   Some candidates confuse it with brute force or DP approaches, thinking it compares pairs or explores subsequences exponentially, leading to O(n^2) or O(2^n) assumptions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant work per element -> O(n) [OK]

Hint: Single pass with constant updates -> O(n)

Common Mistakes:

• Confusing with brute force exponential time
• Assuming nested loops for comparisons
• Thinking sorting is involved