Best Time to Buy and Sell Stock as a Window Problem

"Best Time to Buy and Sell Stock" shows up again and again in Amazon, Meta, Bloomberg phone screens. It is a Easy problem on paper, but the real test is whether you recognize the Sliding Window pattern quickly and code it cleanly. Part 11 of 11 in the Sliding Window arc.

The Problem

Given prices where prices[i] is a stock price on day i, maximize profit from one buy followed by one later sell. Return 0 if no profit is possible. Reportedly one of the most-asked easy questions at Amazon — the filter is whether your one pass is clean.

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5
Buy at 1 (day 2), sell at 6 (day 5). Note 7 then 1 is not a valid trade.

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

Best pair with an ordering constraint (buy before sell) collapses to a growing window with O(1) state: for each day, the best buy is simply the minimum price seen so far. No shrinking, no map — the degenerate window where only the aggregate survives.

The Approach

Sweep once holding min_so_far and best. Each price first offers a sale — profit against min_so_far — then competes to become the new minimum. Order within the loop body does not matter as same-day buy-sell yields zero.

This is also DP in disguise (best profit ending today), which links this arc to the dynamic programming arc later in the series — the patterns are lenses, not boxes.

Python Solution

def max_profit(prices: list[int]) -> int:
    """Max profit from one buy-then-sell; 0 if never profitable."""
    min_so_far = float("inf")
    best = 0
    for p in prices:
        best = max(best, p - min_so_far)
        if p < min_so_far:
            min_so_far = p
    return int(best)

Complexity

• Time: O(n) — single pass, constant work per price
• Space: O(1) — two scalars of state

Interview Tips and Follow-Ups

• Strictly decreasing prices must return 0, not a negative — the most common slip on this question.
• Escalations by number: II (unlimited trades — sum positive deltas), III and IV (k trades — DP), with cooldown (state machine). Know the ladder by name.
• If asked for the actual buy/sell days, store indices alongside the running minimum — a 30-second change worth pre-thinking.

More Sliding Window problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.