Best Time to Buy and Sell Stock

easyTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(1)
Sliding Window1D DPOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Track `minPrice` seen so far; at each day `p`, candidate profit is `p - minPrice`.

2. Complexity Bounds & Proof

Optimal sell at day `i` always pairs with minimum price observed strictly before `i`.

3. Minimal Idiomatic Code

def maxProfit(prices: list[int]) -> int:
    min_p, best = float('inf'), 0
    for p in prices:
        if p < min_p: min_p = p
        else: best = max(best, p - min_p)
    return best

4. Failure Modes & Interview Follow-ups

Pitfalls:- Returning negative profit when strictly decreasing (minimum valid profit is 0).
Follow-ups:- Unlimited transactions (Stock II): accumulate every positive daily delta.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Maximum Subarray (O(N))Best Time to Buy and Sell Stock with Cooldown (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.