One pass with state

A nested loop over a single array is nearly always a sign that the inner loop is recomputing something the outer loop already knew one step earlier. Carry that knowledge forward in a variable or two and the same answer falls out of one scan.

The pattern is one sentence long: keep a summary of the prefix you have already walked, use it at the current element, then extend it to include the current element. Everything after that is choosing what the summary is.

The brute force, and the line it repeats

Given daily prices, find the largest profit from one buy and one later sell. Every pair, no cleverness:

def best_profit_slow(prices):
    best = 0
    for sell in range(len(prices)):
        for buy in range(sell):                     # the inner scan
            best = max(best, prices[sell] - prices[buy])
    return best

The inner line runs n(n−1)/2 times. At n = 10⁵ that is about 5 × 10⁹ subtractions, and at roughly 10⁸ simple operations per second, close to a minute — the arithmetic in complexity by counting rules this out before you type it.

Now look at what the inner loop is for. For sell = 5 it walks prices[0..4] looking for the smallest value. For sell = 4 it walked prices[0..3] looking for the smallest value — the same walk, one element shorter. And the two answers are related:

min(prices[0..4]) = min( min(prices[0..3]), prices[4] )

The inner loop recomputes a number it could have been handed for the cost of one comparison. That is step 3 of the solving loop — name the waste — and naming it here names the fix.

The shape

Most one-pass problems fit this template:

answer = best over i of  f( a[i], S(i) )

where S(i) is a summary of everything before index i. The pass is legal when two things hold:

• S is constant size. One number, or a handful. Not a list that grows.
• S extends in O(1). S(i+1) is computable from S(i) and a[i] alone, without looking back.

For buy-low-sell-high, f(a[i], S) = a[i] − S and S is the running minimum. Both conditions hold, so the quadratic loop collapses to O(n) time and O(1) extra space.

Buy low, sell high, in one pass

def best_profit(prices):
    best = 0
    lowest = float('inf')          # the minimum of everything before today
    for p in prices:
        best = max(best, p - lowest)   # sell today, having bought at that minimum
        lowest = min(lowest, p)        # only now does today become a buy candidate
    return best

On [7, 1, 5, 3, 6, 4]:

i	price	lowest before the read	best after the read
0	7	∞	0
1	1	7	0 (1 − 7 = −6)
2	5	1	4
3	3	1	4 (3 − 1 = 2)
4	6	1	5
5	4	1	5

Six iterations instead of fifteen pair checks, and the gap widens as n²/2 against n: at n = 10⁵ it is 5 × 10⁹ against 10⁵, a factor of fifty thousand.

A single scan over six prices, carrying the minimum seen before the current index and the best profit so far100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

The update order is the bug

State has an invariant, and the invariant is a sentence: lowest is the minimum of every price strictly before the current index. The two lines in the loop body preserve it only in one order. Reverse them:

for p in prices:
    lowest = min(lowest, p)        # wrong: today is now a buy candidate
    best = max(best, p - lowest)   # ...for a sale made today

and lowest now means "the minimum up to and including today", so on the day of a new minimum the code evaluates p − p = 0 and quietly permits a same-day buy and sell.

With best starting at 0 the bug hides, because a zero-profit answer is already allowed. Change the problem to you must transact — best = float('-inf') — and it surfaces: on the strictly falling [7, 6, 4, 3, 1] the correct answer is −1 (buy at 7, sell at 6), and the reversed order returns 0, a trade that never happened.

Say the invariant out loud before you write the loop body. It decides the order, the initial value, and whether the answer is read before or after the update.

The same shape, different state

Largest element to the left of each i. State is a running maximum, read before it is extended — the same two lines with min swapped for max.

Maximum subarray sum. State is the best sum of a subarray ending at the previous index:

def max_subarray(a):
    best = cur = a[0]
    for x in a[1:]:
        cur = max(x, cur + x)      # extend the run, or start fresh at x
        best = max(best, cur)
    return best

On [-2, 1, -3, 4, -1, 2, 1, -5, 4] the running cur goes −2, 1, −2, 4, 3, 5, 6, 1, 5 and best peaks at 6, the subarray [4, -1, 2, 1]. The state is still one number; what changed is the recurrence that extends it.

More than one number. "Where did the best profit occur" carries the minimum and its index — two values, one of them pure bookkeeping. The largest product of two elements needs four. For non-negative input the two largest are enough, but a pair of negatives multiplies to a positive, so the honest state is the two largest and the two smallest, and the answer is max(l1 * l2, s1 * s2). On [-10, -9, 1, 2] the two-largest rule returns 2 × 1 = 2 while the true answer is (−10) × (−9) = 90. Four numbers is still constant size, which is all the pattern asks for — the work is deciding what the input may contain before deciding what to carry.

When one pass is not enough

The moment f needs more than a constant-size summary, the pass stops paying. "How many earlier elements are smaller than a[i]" cannot be answered by any fixed number of variables — that needs an ordered structure.

The other limit is the question. A running summary describes prefixes, so it answers questions about prefixes. Ask about an arbitrary range a[l..r] — thousands of ranges, each a different query — and no single variable carries all of them. Precompute every prefix and subtract instead: that is prefix and suffix arrays.

In an interview

Derive it, do not recall it. Write the quadratic version, then say the sentence that kills it: "the inner loop is scanning for a minimum I already computed one step ago, so I will carry it." That is thirty seconds of narration and it is the part being graded.

Then state the invariant before the loop, in the words you will defend it with: "lowest holds the minimum strictly before i." An interviewer who hears that knows you will get the update order right, and if you slip, they have a precise thing to ask about rather than a vague doubt.

The mistake that loses points: the reversed update, defended with "it passes the example". The example rarely distinguishes them. Test a strictly decreasing input and the case where the answer is allowed to be negative — those two inputs separate the correct order from the plausible one.

Check yourself

For each i you need the largest value strictly to the left of i. Write the invariant and say where the update goes.

The invariant is "best_left is the maximum of a[0..i-1]". Read it into the answer for index i first, then do best_left = max(best_left, a[i]). For i = 0 there is nothing to the left, so the initial value is −∞ or a "not yet defined" marker, not a[0].

n = 10⁵. Roughly how many pair checks does the quadratic version do, and how long does it take at 10⁸ operations per second?

n(n−1)/2 ≈ 5 × 10⁹ checks, so roughly 50 seconds — two orders of magnitude over any interactive budget. The one-pass version does 10⁵ iterations.

Which of these fit one pass with constant state: (a) the maximum gap between consecutive elements, (b) the number of earlier elements greater than a[i], (c) the sum of any range asked at query time?

Only (a): the state is the previous element. (b) needs an ordered structure, because no fixed number of variables summarises "how many are greater". (c) is not about prefixes at all — precompute prefix sums and subtract.