Best Time to Buy And Sell Stock

EASY✓ CHIP-TIMEDLC #121 — FULL STATEMENT ↗

The drill: One price per day, one buy before one sell — squeeze the widest spread out of the chart, or settle for zero if it only ever falls. The warm-up for carrying state through a single pass.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A single stock's price for each day of a stretch arrives in order, and the task is to pick one day to buy and a later day to sell that maximizes profit.

The sale must happen strictly after the purchase — buying and selling on the same day, or selling before buying, is never on the table. At most one buy and one sell pair is allowed across the whole stretch.

If no ordering of a buy before a sell ever turns a profit, because prices only fall or hold steady, the answer is zero rather than a negative number.

EX 01

prices = [3, 8, 1, 9]

→ 8

THE LATE DIP BEATS THE EARLY CLIMB

EX 02

prices = [9, 7, 4, 2]

→ 0

CHART ONLY FALLS — SIT OUT

EX 03

prices = [5]

→ 0

ONE DAY, NO TRADE POSSIBLE

the price list runs from zero up to around one hundred thousand days
prices are non-negative and can repeat across days
the sell day must come strictly after the buy day
when no profitable pair exists, the answer is zero, never negative

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Checking every buy/sell pair repeats work endlessly. Standing on a sell day, what single number about the days behind you decides your best profit?

HINT 2 THE STRUCTURE

For any sell day, the best partner is simply the cheapest price seen so far — one running value, updated as you walk.

HINT 3 ONE STEP FROM THE ANSWER

One pass: keep minSoFar, measure price − minSoFar against the best profit at each step, then fold the current price into minSoFar and keep moving.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FLOOR AND THE SPREADPATTERN · MIN SO FAR, ONE PASSprices = [3, 8, 1, 9]

RUNNING STATE

floor → 3

best → 0

STEP 1

Day 0, price 3, sets the floor — the cheapest price seen so far. Best profit starts at 0.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/best-time-to-buy-and-sell-stock.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        best = 0
        floor = prices[0]  # cheapest price seen so far
        for price in prices[1:]:
            best = max(best, price - floor)
            floor = min(floor, price)
        return best

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 8 LN

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        best = 0
        n = len(prices)
        for buy in range(n):                  # anchor each day as the buy...
            for sell in range(buy + 1, n):    # ...try every later day as the sell
                best = max(best, prices[sell] - prices[buy])
        return best

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public int maxProfit(int[] prices) {
        int best = 0;
        int floor = prices[0]; // cheapest price seen so far
        for (int i = 1; i < prices.length; i++) {
            best = Math.max(best, prices[i] - floor);
            floor = Math.min(floor, prices[i]);
        }
        return best;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 11 LN

class Solution {
    public int maxProfit(int[] prices) {
        int best = 0;
        for (int buy = 0; buy < prices.length; buy++) {
            for (int sell = buy + 1; sell < prices.length; sell++) {
                best = Math.max(best, prices[sell] - prices[buy]);
            }
        }
        return best;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 11 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED