Best Time to Buy and Sell Stock II

▶

Steps

setup

Initialize variables

Set the starting index i to 0 and initialize total profit to 0 before scanning prices.

💡 Initialization is crucial to start scanning from the first day with no profit accumulated yet.

Line:

i = 0
profit = 0
n = len(prices)

💡 We begin with no profit and at the first day to find valleys and peaks.

shrink

Find next valley: compare prices[0] and prices[1]

Check if current price 7 is greater or equal to next price 1 to move i forward to find a valley.

💡 We look for a local minimum where price stops decreasing to buy low.

Line:

while i < n - 1 and prices[i] >= prices[i + 1]:
    i += 1

💡 Since price dropped from 7 to 1, we move forward to find the valley at day 1.

shrink

Find next valley: compare prices[1] and prices[2]

Check if price at day 1 (1) is greater or equal to price at day 2 (5). Since 1 < 5, stop moving i; valley found.

💡 We stop at the valley where price starts to rise.

Line:

while i < n - 1 and prices[i] >= prices[i + 1]:
    i += 1

💡 Valley identified at day 1 with price 1 to buy stock.

insert

Record valley price

Store the valley price 1 as the buy price for the current transaction.

💡 Remembering the valley price is essential to calculate profit after finding the peak.

Line:

valley = prices[i]

💡 We have identified the buy price for the first transaction.

expand

Find next peak: compare prices[1] and prices[2]

Check if price at day 1 (1) is less or equal to price at day 2 (5) to move i forward to find a peak.

💡 We look for a local maximum where price stops increasing to sell high.

Line:

while i < n - 1 and prices[i] <= prices[i + 1]:
    i += 1

💡 Price is rising, so move forward to find the peak.

expand

Find next peak: compare prices[2] and prices[3]

Check if price at day 2 (5) is less or equal to price at day 3 (3). Since 5 > 3, stop moving i; peak found.

💡 We stop at the peak where price starts to drop.

Line:

while i < n - 1 and prices[i] <= prices[i + 1]:
    i += 1

💡 Peak identified at day 2 with price 5 to sell stock.

insert

Record peak price and update profit

Store the peak price 5 and add the profit (5 - 1 = 4) to total profit.

💡 Adding the difference between peak and valley accumulates profit from this transaction.

Line:

peak = prices[i]
profit += peak - valley

💡 Profit after first buy-sell pair is 4.

shrink

Find next valley: compare prices[2] and prices[3]

Check if price at day 2 (5) is greater or equal to price at day 3 (3) to move i forward to find next valley.

💡 After selling, look for next valley to buy again.

Line:

while i < n - 1 and prices[i] >= prices[i + 1]:
    i += 1

💡 Price dropped, so move forward to find next valley.

shrink

Find next valley: compare prices[3] and prices[4]

Check if price at day 3 (3) is greater or equal to price at day 4 (6). Since 3 < 6, stop moving i; valley found.

💡 Stop at valley where price starts to rise again.

Line:

while i < n - 1 and prices[i] >= prices[i + 1]:
    i += 1

💡 Valley identified at day 3 with price 3 to buy stock again.

insert

Record valley price for second transaction

Store the valley price 3 as the buy price for the second transaction.

💡 Remembering this valley price is needed to calculate profit after finding the next peak.

Line:

valley = prices[i]

💡 We have identified the buy price for the second transaction.

expand

Find next peak: compare prices[3] and prices[4]

Check if price at day 3 (3) is less or equal to price at day 4 (6) to move i forward to find a peak.

💡 We look for a local maximum to sell high again.

Line:

while i < n - 1 and prices[i] <= prices[i + 1]:
    i += 1

💡 Price is rising, so move forward to find the peak.

expand

Find next peak: compare prices[4] and prices[5]

Check if price at day 4 (6) is less or equal to price at day 5 (4). Since 6 > 4, stop moving i; peak found.

💡 Stop at the peak where price starts to drop.

Line:

while i < n - 1 and prices[i] <= prices[i + 1]:
    i += 1

💡 Peak identified at day 4 with price 6 to sell stock.

insert

Record peak price and update profit

Store the peak price 6 and add the profit (6 - 3 = 3) to total profit.

💡 Adding the difference between peak and valley accumulates profit from this transaction.

Line:

peak = prices[i]
profit += peak - valley

💡 Profit after second buy-sell pair is 7 (4 + 3).

shrink

Find next valley: compare prices[4] and prices[5]

Check if price at day 4 (6) is greater or equal to price at day 5 (4) to move i forward to find next valley.

💡 Look for next valley to buy again if possible.

Line:

while i < n - 1 and prices[i] >= prices[i + 1]:
    i += 1

💡 Price dropped, so move forward to find next valley.

prune

Check if end reached

Since i is now at the last index (5), the while loop condition i < n - 1 fails and the algorithm ends.

💡 No more days to buy or sell, so we finish.

Line:

while i < n - 1:

💡 Algorithm terminates with total profit calculated.

reconstruct

Return total profit

Return the accumulated profit 7 as the maximum profit achievable by multiple transactions.

💡 The final answer is the sum of all profitable buy-sell pairs found.

Line:

return profit

💡 The algorithm correctly computed the maximum profit 7.

def maxProfit(prices):
    i = 0  # STEP 1: initialize index
    profit = 0  # STEP 1: initialize profit
    n = len(prices)  # STEP 1: get length
    while i < n - 1:  # STEP 15: loop until end
        while i < n - 1 and prices[i] >= prices[i + 1]:  # STEP 2,3,8,9,14: find valley
            i += 1  # STEP 2,8,14: move i right
        valley = prices[i]  # STEP 4,10: record valley
        while i < n - 1 and prices[i] <= prices[i + 1]:  # STEP 5,6,11,12: find peak
            i += 1  # STEP 5,11: move i right
        peak = prices[i]  # STEP 7,13: record peak
        profit += peak - valley  # STEP 7,13: add profit
    return profit  # STEP 16: return total profit

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

📊

Best Time to Buy and Sell Stock II - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how the greedy approach accumulates profit by capturing every profitable upward price movement.

setup

i

7

0

1

1

5

2

3

3

6

4

4

5

Result: 0

move_right

7

0

i

1

1

5

2

3

3

6

4

4

5

Result: 0

compare

7

0

i

1

1

5

2

3

3

6

4

4

5

Result: 0

record

7

0

i

1

1

5

2

3

3

6

4

4

5

Result: 0

move_right

7

0

1

1

i

5

2

3

3

6

4

4

5

Result: 0

compare

7

0

1

1

i

5

2

3

3

6

4

4

5

Result: 0

record

7

0

1

1

i

5

2

3

3

6

4

4

5

Result: 4

move_right

7

0

1

1

5

2

i

3

3

6

4

4

5

Result: 4

compare

7

0

1

1

5

2

i

3

3

6

4

4

5

Result: 4

record

7

0

1

1

5

2

i

3

3

6

4

4

5

Result: 4

move_right

7

0

1

1

5

2

3

3

i

6

4

4

5

Result: 4

compare

7

0

1

1

5

2

3

3

i

6

4

4

5

Result: 4

record

7

0

1

1

5

2

3

3

i

6

4

4

5

Result: 7

move_right

7

0

1

1

5

2

3

3

6

4

i

4

5

Result: 7

prune

7

0

1

1

5

2

3

3

6

4

i

4

5

Result: 7

record

7

0

1

1

5

2

3

3

6

4

4

5

Result: 7

Key Takeaways

✓ The algorithm accumulates profit by capturing every upward price movement between valleys and peaks.

This insight is hard to see from code alone because the pointer movements and comparisons reveal the greedy logic visually.

✓ Pointer 'i' moves forward step-by-step to find local minima (valleys) and maxima (peaks) in the price array.

Visualizing each pointer move clarifies how the algorithm decides when to buy and sell.

✓ Profit is updated only after both a valley and a peak are found, ensuring only profitable transactions are counted.

Seeing the exact moment profit updates helps understand why partial or non-profitable moves are ignored.

Practice

1. You are given a sequence of integers and need to find the length of the longest subsequence where the differences between successive elements strictly alternate between positive and negative. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Dynamic Programming with a 2D table tracking subsequence lengths for each index and difference sign

B. Brute force recursion exploring all subsequences and checking alternating differences

C. Greedy approach tracking the direction of the last difference and counting peaks and valleys

D. Sliding window approach maintaining a contiguous alternating difference substring

Solution

1. Step 1: Understand problem constraints

   The problem requires the longest subsequence with alternating positive and negative differences, not necessarily contiguous.

2. Step 2: Identify optimal approach

   Dynamic programming is possible but less efficient; brute force is exponential; sliding window fails because subsequence need not be contiguous. The greedy approach tracking last difference direction and counting peaks and valleys achieves O(n) time and O(1) space optimally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy with direction tracking matches problem requirements [OK]

Hint: Longest alternating difference subsequence -> greedy direction tracking

Common Mistakes:

• Confusing subsequence with substring
• Assuming DP is always needed
• Trying brute force without pruning

2. What is the time complexity of the optimal min-heap based algorithm for finding the minimum number of platforms required for n trains?

medium

A. O(n²) due to nested loops checking all train pairs

B. O(n) because each train is processed once

C. O(n log n) due to sorting and heap operations for each train

D. O(n log k) where k is the maximum number of platforms needed

Solution

1. Step 1: Identify sorting cost

   Sorting n trains by arrival time costs O(n log n).

2. Step 2: Analyze heap operations

   Each train causes at most one push and one pop on the heap, each O(log n), so total O(n log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting + heap operations dominate complexity [OK]

Hint: Sorting + heap push/pop per train -> O(n log n) [OK]

Common Mistakes:

• Assuming O(n) ignoring sorting and heap costs
• Confusing heap size k with n for complexity
• Mistaking nested loops for optimal approach complexity

3. What is the time complexity of the optimal greedy solution for Two City Scheduling that sorts by cost difference and assigns people in a single pass?

medium

A. O(n^2) because of nested loops to assign people

B. O(n log n) due to sorting the list of 2n people

C. O(n) since assignment is done in one pass after sorting

D. O(n log n) including sorting and constant time assignment

Solution

1. Step 1: Identify sorting cost

   Sorting 2n people by cost difference takes O(n log n) time.

2. Step 2: Identify assignment cost

   Assigning people in a single pass is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting dominates, total complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity [OK]

Common Mistakes:

• Assuming assignment is nested loop causing O(n^2)
• Ignoring sorting cost and claiming O(n)
• Confusing space complexity with time complexity

4. Suppose the Gas Station problem is modified so that you can refill gas multiple times at the same station (i.e., unlimited reuse), and you want to find if any start station allows completing the circle with this new rule. Which approach correctly adapts to this variant?

hard

A. Check if total gas is at least total cost; if yes, return any station since reuse allows completion

B. Modify the algorithm to allow multiple passes over the stations until tank is non-negative

C. Use a graph cycle detection algorithm to find a feasible cycle with unlimited refills

D. Use the original greedy approach without changes; it still works correctly

Solution

1. Step 1: Understand unlimited refill effect

   With unlimited refills, the only constraint is total gas >= total cost; any station can be start.

2. Step 2: Simplify solution

   Since reuse removes the need to track tank drops, just check total gas vs cost and return any index if feasible.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Unlimited refill means any station works if total gas suffices [OK]

Hint: Unlimited refill means total gas check suffices [OK]

Common Mistakes:

• Trying to simulate multiple passes
• Using original greedy without adaptation
• Overcomplicating with graph algorithms

5. Suppose the problem is modified: instead of finding the largest monotone increasing digits number ≤ n, you want the largest monotone increasing digits number ≤ n that can reuse digits any number of times (digits can be repeated arbitrarily). Which approach correctly adapts the algorithm?

hard

A. Use the original greedy algorithm but allow digits after marker to be any digit less than or equal to the digit at marker-1

B. Sort the digits of n and build the largest monotone number by repeating the smallest digit as many times as needed

C. Use a backtracking approach to generate all monotone numbers with digits ≤ those in n, allowing reuse, and pick the largest ≤ n

D. Modify the greedy algorithm to decrement digits and set trailing digits to the digit at marker-1 instead of 9

Solution

1. Step 1: Understand digit reuse changes problem nature

   Allowing reuse means digits can be repeated arbitrarily, so greedy digit decrement and trailing 9 assignment no longer guarantee largest monotone number ≤ n.

2. Step 2: Backtracking enumerates all monotone numbers with digit reuse

   Backtracking can generate all monotone numbers with digits ≤ those in n, allowing reuse, then pick the largest ≤ n.

3. Step 3: Other options fail to handle reuse or produce incorrect numbers

   Sorting digits or modifying trailing digits to marker-1 digit does not guarantee largest monotone number with reuse.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Backtracking correctly handles reuse and monotonicity constraints [OK]

Hint: Digit reuse breaks greedy; backtracking needed for correctness [OK]

Common Mistakes:

• Trying to adapt greedy without full enumeration
• Assuming trailing digits can be set to 9 or marker digit
• Ignoring exponential complexity of reuse