Best Time to Buy and Sell Stock (1 tx)

▶

Steps

setup

Initialize min_price and max_profit

Set min_price to the price on day 0 (7) and max_profit to 0 before starting iteration.

💡 We start with the first day's price as the minimum since we haven't seen any other prices yet.

Line:

min_price = prices[0]
max_profit = 0

💡 Initial values establish the baseline for comparisons in subsequent days.

fill_cells

Process day 1 price = 1: Compare with min_price

Compare price 1 with current min_price 7 to decide whether to update min_price or max_profit.

💡 We check if today's price is lower than the minimum price seen so far.

Line:

if prices[i] < min_price:

💡 Tracking the lowest price so far is crucial to maximize profit later.

fill_cells

Update min_price to 1

Since price 1 is less than min_price 7, update min_price to 1 and keep max_profit 0.

💡 Updating min_price helps find a better buy day for future profits.

Line:

min_price = prices[i]

💡 The algorithm remembers the lowest price to calculate profits later.

fill_cells

Process day 2 price = 5: Calculate profit and update max_profit

Price 5 is not less than min_price 1, so calculate profit = 5 - 1 = 4 and update max_profit from 0 to 4.

💡 Selling today at price 5 yields a profit of 4 if bought at min_price 1.

Line:

else:
    max_profit = max(max_profit, prices[i] - min_price)

💡 We track the best profit achievable so far by selling on the current day.

fill_cells

Process day 3 price = 3: Calculate profit and compare

Price 3 is not less than min_price 1, calculate profit = 3 - 1 = 2, which is less than current max_profit 4, so max_profit stays 4.

💡 Selling today yields less profit than the best so far, so no update.

Line:

else:
    max_profit = max(max_profit, prices[i] - min_price)

💡 We only update max_profit when a better profit is found.

fill_cells

Process day 4 price = 6: Calculate profit and update max_profit

Price 6 is not less than min_price 1, calculate profit = 6 - 1 = 5, which is greater than max_profit 4, update max_profit to 5.

💡 Selling today yields the best profit so far, so we update max_profit.

Line:

else:
    max_profit = max(max_profit, prices[i] - min_price)

💡 The algorithm finds a better selling day to maximize profit.

fill_cells

Process day 5 price = 4: Calculate profit and compare

Price 4 is not less than min_price 1, calculate profit = 4 - 1 = 3, which is less than max_profit 5, so max_profit stays 5.

💡 Selling today yields less profit than the best so far, so no update.

Line:

else:
    max_profit = max(max_profit, prices[i] - min_price)

💡 The algorithm maintains the best profit found so far.

reconstruct

Iteration complete: Return max_profit

After processing all days, return the maximum profit found, which is 5.

💡 The final max_profit is the answer to the problem.

Line:

return max_profit

💡 The algorithm efficiently computes the best profit with a single pass.

summary

Summary: min_price and max_profit progression

Review how min_price and max_profit changed over each day to understand the algorithm's flow.

💡 Seeing the progression helps solidify understanding of the state machine approach.

💡 The algorithm maintains and updates two variables to find the optimal buy-sell pair efficiently.

final

Final answer: Maximum profit is 5

The maximum profit achievable with one transaction on the given prices is 5.

💡 This confirms the algorithm's correctness and efficiency.

💡 The algorithm solves the problem in linear time with constant space.

def maxProfit(prices):
    min_price = prices[0]  # STEP 1
    max_profit = 0        # STEP 1
    for i in range(1, len(prices)):
        if prices[i] < min_price:  # STEP 2,3,4,5,6,7
            min_price = prices[i]  # STEP 2,3,5
        else:
            max_profit = max(max_profit, prices[i] - min_price)  # STEP 4,6,7
    return max_profit  # STEP 8

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

📊

Best Time to Buy and Sell Stock (1 tx) - Watch the Algorithm Execute, Step by Step

Watching each update to min_price and max_profit helps you understand how the algorithm efficiently finds the best buy-sell pair without nested loops.

Item 0 - wt:7 val:0

i\w	0	1	2	3	4	5
i=0	[7,0]	?	?	?	?	?

min_price=7, max_profit=0

Item 1 - wt:1 val:0

i\w	0	1	2	3	4	5
i=0	[7,0]	[1,0]	?	?	?	?

min_price updated to 1

Item 1 - wt:1 val:0

i\w	0	1	2	3	4	5
i=0	[7,0]	[1,0]	?	?	?	?

min_price=1, max_profit=0

Item 2 - wt:5 val:4

i\w	0	1	2	3	4	5
i=0	[7,0]	[1,0]	[1,4]	?	?	?

max_profit updated to 4

Item 3 - wt:3 val:4

i\w	0	1	2	3	4	5
i=0	[7,0]	[1,0]	[1,4]	[1,4]	?	?

max_profit unchanged at 4

Item 4 - wt:6 val:5

i\w	0	1	2	3	4	5
i=0	[7,0]	[1,0]	[1,4]	[1,4]	[1,5]	?

max_profit updated to 5

Item 5 - wt:4 val:5

i\w	0	1	2	3	4	5
i=0	[7,0]	[1,0]	[1,4]	[1,4]	[1,5]	[1,5]

max_profit unchanged at 5

Item 5 - wt:4 val:5

i\w	0	1	2	3	4	5
i=0	[7,0]	[1,0]	[1,4]	[1,4]	[1,5]	[1,5]

Answer: max_profit=5

Initializing dp array

i\w	0	1	2	3	4	5
i=0	[7,0]	[1,0]	[1,4]	[1,4]	[1,5]	[1,5]

min_price and max_profit states

Item 5 - wt:4 val:5

i\w	0	1	2	3	4	5
i=0	[7,0]	[1,0]	[1,4]	[1,4]	[1,5]	[1,5]

Final max_profit = 5

Key Takeaways

✓ Tracking the minimum price seen so far allows the algorithm to find the best buy day efficiently.

Without this insight, one might try nested loops, which are less efficient and harder to visualize.

✓ The maximum profit is updated only when a better selling day is found, showing a linear progression.

This step-by-step update clarifies how the algorithm avoids unnecessary calculations.

✓ The decision to update min_price or max_profit depends on a simple comparison, illustrating a clear state machine behavior.

Seeing this decision in action helps understand the branching logic that drives the algorithm.

Practice

1. What is the time and space complexity of the optimal space-optimized bottom-up DP solution for the Best Time -- Cooldown problem with input size n (number of days)?

medium

A. Time: O(n), Space: O(1)

B. Time: O(2^n), Space: O(n)

C. Time: O(n), Space: O(n)

D. Time: O(n²), Space: O(n)

Solution

1. Step 1: Identify time complexity

   The algorithm iterates once through prices array, performing constant work per iteration -> O(n) time.

2. Step 2: Identify space complexity

   Only constant variables (hold, cool, free) are used, no arrays -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass, constant variables -> O(n) time and O(1) space [OK]

Hint: One pass with constant states means O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing recursion stack space with iterative space
• Assuming DP arrays used in bottom-up

2. The following code attempts to count the number of ways to decode a string. Which line contains a subtle bug that causes incorrect results for inputs containing '0'?

medium

A. if s[i] != '0':

B. curr += prev1 # inside two_digit check

C. if 10 <= two_digit <= 26:

D. prev2, prev1 = prev1, curr

Solution

1. Step 1: Identify two-digit addition logic

   The two-digit check should add prev2, not prev1, because it represents ways two steps back.

2. Step 2: Understand impact on '0' handling

   Adding prev1 instead of prev2 causes overcounting or invalid counts when '0' appears, e.g., '10' or '20'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct two-digit addition uses prev2, not prev1 [OK]

Hint: Two-digit addition must add prev2, not prev1 [OK]

Common Mistakes:

• Confusing prev1 and prev2 in two-digit addition

3. What is the time complexity of the top-down memoized recursive solution for the House Robber problem with input size n, and why might some candidates mistakenly think it is exponential?

medium

A. O(n^2) due to overlapping subproblems recomputed multiple times

B. O(2^n) because each call branches into two recursive calls

C. O(n) because memoization ensures each index is computed once

D. O(n log n) because recursion depth is logarithmic

Solution

1. Step 1: Analyze recursion with memoization

   Memoization caches results for each index i, so robFrom(i) is computed once per i.

2. Step 2: Determine total calls and complexity

   Since i ranges from 0 to n-1, total calls are O(n), each O(1) work -> O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Without memoization, calls explode exponentially; memoization reduces to linear [OK]

Hint: Memoization reduces exponential calls to linear by caching [OK]

Common Mistakes:

• Assuming recursion always exponential
• Ignoring memoization effect

4. Consider the following buggy code for Jump Game II. Which line contains the subtle bug that causes incorrect results for input arrays of length 1?

medium

A. Line 2: n = len(nums)

B. Line 9: return jumps

C. Line 3: jumps = 0

D. Line 5: for i in range(n - 1):

Solution

1. Step 1: Analyze loop range for single-element array

   When n=1, range(n-1) = range(0), so the loop does not run, and jumps remains 0.

2. Step 2: Check if jumps=0 is correct for single-element input

   For an array of length 1, minimum jumps should be 0 (already at last index). The code returns 0, which is correct. However, if the problem expects at least one jump or code elsewhere assumes the loop runs, this can cause issues. The subtle bug is that the loop does not run for n=1, so no updates happen. If code elsewhere expects jumps increment, this is a problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop skipping for n=1 causes edge case bugs [OK]

Hint: Loop range excludes last index, skip for single-element arrays [OK]

Common Mistakes:

• Not handling single-element arrays properly
• Assuming loop always runs at least once
• Returning jumps without base case check

5. What is the time complexity of the optimal greedy solution for the Jump Game problem, and why?

medium

A. O(n) because it iterates through the array once updating maxReach

B. O(n^2) because each position may check multiple jumps

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

D. O(2^n) because of exploring all jump paths recursively

Solution

1. Step 1: Identify loop structure

   The greedy solution iterates through the array once, updating maxReach in O(1) time per iteration.

2. Step 2: Confirm no nested loops or recursion

   There are no nested loops or recursion, so total time is linear in array length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass over array -> O(n) time [OK]

Hint: Greedy uses single pass, no nested loops [OK]

Common Mistakes:

• Confusing brute force with greedy complexity
• Assuming sorting is needed
• Forgetting recursion stack space