Week 2 · Sliding Window

Best Time to Buy and Sell Stock

Given daily stock prices, choose one buy day and one later sell day to maximize profit.

Easy Sliding Window Week 2 Practice runner

Frame the problem

You may complete at most one transaction.
The sell day must come after the buy day.
Return 0 when no profitable transaction exists.

1. Reveal example inputs and outputs

Example 1

Input:

max_profit([
  7,
  1,
  5,
  3,
  6,
  4
])

Output:

Example 2

Input:

max_profit([
  7,
  6,
  4,
  3,
  1
])

Output:

2. Brute force first

What would checking every buy/sell pair cost? Which single value from the past is enough for the current sell day?

3. Reveal the insight ladder

For each day, the best buy is the lowest price before it.
Track min_price as you scan left to right.
Candidate profit is current price minus min_price.
Update the best profit and then keep the lowest buy price for future days.

4. Dry run before code

prices = [7, 1, 5, 3, 6, 4].
Min price becomes 1 on day 2.
Selling at 6 gives profit 5, which is best.

5. Reveal final Python solution

def max_profit(prices):
    min_price = float("inf")
    best = 0
    for price in prices:
        best = max(best, price - min_price)
        min_price = min(min_price, price)
    return best

Complexity: Time O(n), space O(1).

Interview narration

The invariant is the cheapest legal buy before the current day.
That lets every day be considered as a sell day once.
A descending price list naturally returns zero.

Common traps

Allowing sell before buy.
Resetting the best profit when a lower price appears.
Returning a negative profit.

Follow-up drills

1. What changes with unlimited transactions?

You can add every positive day-to-day gain, because each upward edge can be treated as part of a buy/sell sequence.

2. What changes with at most two transactions?

Use DP states for first buy, first sell, second buy, and second sell, or split prefix/suffix best profits.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.