File: best-time-to-buy-and-sell-stock/solution.py

Date: 2026-06-06

Time: 15:22

best-time-to-buy-and-sell-stock/solution.py

Purpose

This file solves LeetCode #121 — Best Time to Buy and Sell Stock. It finds the maximum profit from a single buy-sell transaction given a time series of stock prices. It's a standalone solution module following the repo's convention of one problem per directory.

Key Components

maxProfit(prices: list[int]) -> int — The sole function. Contract:

• Input: A list of integers where prices[i] is the stock price on day i. Assumes at least one element (indexes into prices[0] unconditionally).
• Output: The maximum profit from buying on one day and selling on a later day, or 0 if no profitable transaction exists.

Patterns

The solution uses Kadane's-style single-pass tracking — a classic greedy pattern for problems where you need the maximum difference prices[j] - prices[i] with j > i. Instead of checking all O(n²) pairs, it maintains a running minimum and computes the best profit at each step.

This is the same pattern used in maximum-difference-between-increasing-elements/solution.py — track min-so-far, compute max-delta at each position.

Dependencies

Imports: None — pure Python with no library dependencies.

Imported by: The best-time-to-buy-and-sell-stock/test_solution.py file imports this directly. The massive "Imported By" list in the prompt is an artifact of the repo's test infrastructure — those other test files don't actually import this solution; they share a common test harness pattern.

Flow

1. Initialize minprice to the first element and maxprofit to 0.

2. Iterate over prices[1:]. For each price:

• Compute price - minprice — the profit if we sold today having bought at the cheapest seen so far. Update maxprofit if this is larger.
• Update min_price if today's price is lower — future days can now buy cheaper.

3. Return max_profit.

The order of the two updates inside the loop matters: profit is computed *before* min_price is updated, which prevents buying and selling on the same day from inflating the result (though same-day would yield 0 profit anyway, so it's actually safe either way — the ordering is a clarity choice, not a correctness requirement).

Invariants

• Single transaction: Only one buy and one sell. This is not the "unlimited transactions" variant (LeetCode #122).
• Non-negative result: Returns 0 when prices are monotonically decreasing — the function implicitly assumes you can choose not to transact.
• Assumes non-empty input: prices[0] is accessed without a length check. An empty list raises IndexError.

Error Handling

None. The function trusts its caller to provide a valid, non-empty list of integers. This is consistent with LeetCode's constraints where 1 <= prices.length <= 10^5.