Best Time to Buy and Sell Stock II

📋

Problem

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?

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

Edge cases: Single day prices [5] → 0 profit because no transactions possibleAll prices equal [3,3,3,3] → 0 profit because no profitable transactionsPrices with multiple equal peaks [1,2,2,2,3] → profit should count all increases

</>

IDE

def maxProfit(prices: list[int]) -> int:public int maxProfit(int[] prices)int maxProfit(vector<int> &prices)function maxProfit(prices)

def maxProfit(prices):
    # Write your solution here
    pass

class Solution {
    public int maxProfit(int[] prices) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxProfit(vector<int> &prices) {
    // Write your solution here
    return 0;
}

function maxProfit(prices) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Only one transaction allowed or no transactions counted.✅ Sum all positive differences between consecutive days instead of single max transaction.

Wrong: Incorrect positive profit on constant pricesAdding zero or negative differences as profit.✅ Add only strictly positive differences: if prices[i] > prices[i-1].

Wrong: Crash or errorNo handling of empty input array.✅ Return 0 immediately if prices array is empty.

Wrong: TLE or timeoutUsing brute force or recursive exponential approach.✅ Implement O(n) greedy solution summing positive differences.

Wrong: Missed last profitable transactionOff-by-one error in iteration range.✅ Iterate through all pairs of consecutive days up to last index.

✓

Test Cases

Now test your code on boundary inputs like empty or single-element arrays.

Try tricky cases with equal prices and multiple peaks to catch subtle bugs.

Prepare for large inputs that require efficient O(n) solutions.

t1_01basic

Input{"prices":[7,1,5,3,6,4]}

Expected7

⏱ Performance - must finish in 2000ms

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.

💡 Consider summing all positive price differences between consecutive days.

💡 Use a greedy approach to add profit whenever prices[i] > prices[i-1].

💡 Iterate through prices and add (prices[i] - prices[i-1]) if positive.

Why it failed: Incorrect profit indicates missing some profitable transactions. Fix by summing all positive consecutive differences, not just one transaction.

✓ Correctly sums all profitable transactions.

t1_02basic

Input{"prices":[1,2,3,4,5]}

Expected4

⏱ Performance - must finish in 2000ms

Prices increase every day; buy day 1, sell day 5 for max profit 4, or sum daily gains (1+1+1+1=4).

💡 Check if summing all positive consecutive differences works for strictly increasing prices.

💡 Greedy approach applies: add each increase between consecutive days.

💡 Sum (2-1)+(3-2)+(4-3)+(5-4) = 4.

Why it failed: Failing this means not summing all positive increments. Fix by adding all positive diffs between consecutive days.

✓ Correctly handles strictly increasing prices by summing all increments.

t2_01edge

Input{"prices":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty price list means no transactions possible, profit is 0.

💡 Check behavior when prices array is empty.

💡 Return 0 if no prices are given.

💡 Add a guard clause: if not prices, return 0.

Why it failed: Code crashes or returns non-zero on empty input. Fix by returning 0 immediately if prices is empty.

✓ Handles empty input gracefully with zero profit.

t2_02edge

Input{"prices":[5]}

Expected0

⏱ Performance - must finish in 2000ms

Single day price means no sell possible, profit is 0.

💡 Consider the case with only one price.

💡 No transactions possible with single day, profit must be 0.

💡 Return 0 if prices length is 1.

Why it failed: Returns non-zero profit for single price input. Fix by ensuring no transactions if prices length < 2.

✓ Correctly returns zero profit for single day.

t2_03edge

Input{"prices":[3,3,3,3]}

Expected0

⏱ Performance - must finish in 2000ms

All prices equal, no profitable transactions, profit is 0.

💡 Check if code sums only positive differences.

💡 No positive differences here, so profit should be 0.

💡 Ensure code skips zero or negative differences.

Why it failed: Returns positive profit when prices are constant. Fix by adding only strictly positive differences.

✓ Correctly returns zero profit for constant prices.

t3_01corner

Input{"prices":[1,2,2,2,3]}

Expected2

⏱ Performance - must finish in 2000ms

Profit counts all increases: (2-1)=1 and (3-2)=1, total 2. Flat prices do not add profit.

💡 Check how equal consecutive prices are handled.

💡 Only add strictly positive differences, ignore zero differences.

💡 Sum (2-1) + (3-2) = 2, skip zero diffs.

Why it failed: Counting zero differences as profit causes overcount. Fix by adding only strictly positive differences.

✓ Correctly ignores zero differences and sums only positive increments.

t3_02corner

Input{"prices":[1,2,1,2,1,2]}

Expected3

⏱ Performance - must finish in 2000ms

Profit sums all positive diffs: (2-1)+(2-1)+(2-1)=3.

💡 Beware of greedy traps that try to buy once and sell once only.

💡 Sum all positive consecutive differences to maximize profit.

💡 Add (2-1)+(2-1)+(2-1) = 3.

Why it failed: Greedy trap: only one transaction counted. Fix by summing all positive consecutive differences.

✓ Correctly sums multiple buy-sell pairs for max profit.

t3_03corner

Input{"prices":[3,2,6,5,0,3]}

Expected7

⏱ Performance - must finish in 2000ms

Profit = (6-2)+(3-0)=4+3=7 by buying low and selling high multiple times.

💡 Check for off-by-one errors in iteration over prices.

💡 Ensure all positive differences are included, not skipping last day.

💡 Sum (6-2) + (3-0) = 7 correctly.

Why it failed: Off-by-one error causes missing last profitable transaction. Fix by iterating to last index and summing all positive diffs.

✓ Correctly includes all profitable transactions.

t4_01performance

Input{"prices":[10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999,10000,9999]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, alternating high-low prices to test O(n) greedy solution runs within 2 seconds.

💡 Use O(n) greedy approach summing positive diffs.

💡 Avoid nested loops or recursion that cause exponential time.

💡 Iterate once through prices, adding positive increments.

Why it failed: TLE caused by exponential or quadratic complexity. Fix by implementing O(n) greedy sum of positive differences.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following Python function that calculates the minimum number of platforms needed. Given the input arrivals = [900, 940, 950] and departures = [910, 1200, 1120], what is the value of max_platforms after processing the second train (index 1)?

easy

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Sort trains by arrival time

   Sorted trains: [(900, 910), (940, 1200), (950, 1120)]

2. Step 2: Process trains up to index 1

   After first train: heap=[910], max_platforms=1 Second train arrival=940, heap top=910 ≤ 940, pop 910 Push 1200, heap=[1200], max_platforms=max(1,1)=1 Since question asks after second train, max_platforms=1

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap size after second train is 1, max_platforms updated to 1 [OK]

Hint: Heap pops departures ≤ arrival before push [OK]

Common Mistakes:

• Not popping from heap before push
• Confusing max_platforms update timing
• Off-by-one in iteration

2. You are given a numeric string and an integer k. The task is to remove exactly k digits from the string so that the resulting number is the smallest possible. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Backtracking to try all combinations of digits to remove

B. Dynamic Programming that tries all subsequences of length n-k and picks the smallest

C. Sorting the digits and removing the largest k digits

D. Greedy algorithm using a stack to maintain a monotonically increasing sequence of digits

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing digits to minimize the resulting number, which suggests a greedy approach to decide which digits to remove as we scan the string.

2. Step 2: Why greedy with stack works

   The stack-based greedy approach maintains a monotonically increasing sequence by popping larger digits when a smaller digit is encountered, ensuring the smallest possible prefix at each step.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy stack approach is known optimal for this problem [OK]

Hint: Monotonic stack ensures smallest prefix greedily [OK]

Common Mistakes:

• Assuming sorting digits works ignores digit order
• Thinking DP is needed for this greedy problem
• Trying brute force is too slow for large inputs

3. Consider the following Python code snippet implementing the optimal solution to remove k digits from a number string to get the smallest number. What is the output of removeKdigits("1432", 2)?

def removeKdigits(num: str, k: int) -> str:
    builder = []
    for digit in num:
        while k > 0 and builder and builder[-1] > digit:
            builder.pop()
            k -= 1
        builder.append(digit)
    while k > 0:
        builder.pop()
        k -= 1
    result = ''.join(builder).lstrip('0')
    return result if result else '0'

easy

A. "14"

B. "13"

C. "12"

D. "32"

Solution

1. Step 1: Trace builder and k during iteration

   Start with builder = [], k=2 - digit='1': builder=['1'], k=2 - digit='4': '4' > '1', append: builder=['1','4'], k=2 - digit='3': '3' < '4', pop '4', k=1; append '3': builder=['1','3'] - digit='2': '2' < '3', pop '3', k=0; append '2': builder=['1','2']

2. Step 2: Remove remaining k and finalize

   k=0, no more pops. Result = '12' after stripping leading zeros.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected smallest number after removing 2 digits [OK]

Hint: Pop larger digits when smaller digit found until k=0 [OK]

Common Mistakes:

• Not popping enough digits when smaller digit appears
• Removing digits from front only
• Forgetting to strip leading zeros

4. The following code attempts to remove k digits from a number string to get the smallest number. Which line contains a subtle bug that causes incorrect results on inputs with leading zeros?

def removeKdigits(num: str, k: int) -> str:
    builder = []
    for digit in num:
        while k > 0 and builder and builder[-1] > digit:
            builder.pop()
            k -= 1
        builder.append(digit)
    while k > 0:
        builder.pop()
        k -= 1
    result = ''.join(builder)  # Bug here
    return result if result else '0'

medium

A. Line where digits are popped inside the for loop

B. Line where leading zeros are not stripped from the final result

C. Line where remaining digits are popped after the loop

D. Line where digits are appended to builder

Solution

1. Step 1: Identify missing leading zero removal

   The code joins builder into a string but does not strip leading zeros, which can cause incorrect output like "0012" instead of "12".

2. Step 2: Why this is a bug

   Leading zeros must be removed to get the correct smallest number representation; otherwise, the output is invalid.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Adding .lstrip('0') fixes the bug [OK]

Hint: Always strip leading zeros before returning result [OK]

Common Mistakes:

• Forgetting to strip leading zeros
• Removing digits incorrectly in the loop
• Not popping remaining digits when k > 0

5. The following code attempts to implement the optimal wiggle subsequence algorithm. Identify the line containing the subtle bug that causes incorrect results on inputs with consecutive equal elements.

def wiggleMaxLength(nums):
    if not nums:
        return 0
    count = 1
    last_diff = 0
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and last_diff < 0) or (diff < 0 and last_diff > 0):
            count += 1
            last_diff = diff
    return count

medium

A. Line 6: Using strict inequalities (last_diff < 0 and last_diff > 0) instead of inclusive (<= 0 and >= 0)

B. Line 3: Initializing count to 1 instead of 0

C. Line 7: Updating last_diff inside the if condition

D. Line 2: Returning 0 if nums is empty

Solution

1. Step 1: Understand the condition for counting wiggles

   The condition must allow last_diff to be zero or equal to zero to handle initial or equal consecutive elements correctly.

2. Step 2: Identify the bug

   Using strict inequalities excludes cases where last_diff is zero, causing the algorithm to skip valid wiggles after equal elements, leading to incorrect counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inclusive inequalities fix counting on equal consecutive elements [OK]

Hint: Use <= 0 and >= 0 to handle zero last_diff correctly

Common Mistakes:

• Using strict inequalities causing missed wiggles
• Incorrect initialization of counters
• Updating last_diff outside condition