Arrays & Strings · Stage 1 of 3
Single-Pass State Tracking
Carry one running value (min, max, or best so far) through a scan
Foundations
An array stores items in contiguous, numbered slots called indices. An index counts how many steps a slot sits from the start, so the first slot is index 0. In nums = [7, 1, 5, 3, 6], the 1st element is nums[0] = 7 and the 4th is nums[3] = 3. An array of n elements runs from index 0 to n - 1, so these five run from 0 to 4.
address(i) = base + i × 4
nums[3] → 1000 + 3 × 4 = 1012
nums[3] sits at 1000 + 3 × 4 = 1012: one multiplication and one addition, not a search. Python lists store 8-byte references in the same contiguous layout, so indexing is still O(1).Contiguous means side by side in memory, so nums[i] sits exactly i steps past the start. The computer finds it with one multiplication and one addition, as the diagram shows, which makes reading any index O(1), for 5 elements or 5 million. A string works the same way for characters. The slots also never reshuffle on their own, so a left-to-right scan meets nums[0] through nums[4] in the same order every time.
Single-pass state tracking uses that order. As you scan, you carry one running value in a variable, called the state, chosen for the question you are answering: the smallest so far for a minimum, a running total for a sum. The state is a compression. Once an element has updated it, the raw element can be forgotten, because the state already holds everything later steps need from it. Memory stays O(1), and the loop never steps backward.
nums
smallest = 1; a sum scan would reduce them to total = 13. The next step needs only that number.Case Scenario
The problem
Best Time to Buy and Sell Stock
prices[i] is the price of a stock on day i. You may buy once and sell once later. Return the maximum profit, or 0 if no profit is possible.
- Input
- prices = [7, 1, 5, 3, 6, 4]
- Output
- 5
Here the array is a timeline: index i is day i, and prices[i] is the stock's price that day. Because indexing starts at 0, the first price, prices[0] = 7, is day 0, and the last, prices[5] = 4, is day 5. Scanning left to right walks forward through time, so a sale on day i can only pair with a buy from an earlier day.
With six prices, you can spot the best trade by eye: buy on day 1 (prices[1] = 1) and sell on day 4 (prices[4] = 6), for a profit of 5. Code that checks every option the same way uses two nested loops: an outer loop picks the buy day, and an inner loop tries every later day as the sale. That is 15 pairs for 6 days and n(n - 1)/2 for n days, which is O(n²). Step through the passes below to see where that work goes.
Step through it
Interactive Brute-Force Tracer: Watch the Redundant Rescans
prices
day 0
7, the buy dayday 1
1, checked as a sell dayday 2
5, checked as a sell dayday 3
3, checked as a sell dayday 4
6, checked as a sell dayday 5
4, checked as a sell day
- buy day (i)
- sell days the inner loop checks (j)
- earlier days, never looked back at
- Outer pass
- i = 0prices[0] = 7
- Checked this pass
- 5days 1–5
- Checked so far
- 5 of 15
Pass 0 pairs day 0's price, 7, with every later day: 5 comparisons, each reading its price for the first time.
Approach 1 · Brute force
Try every pair of days
This is the code the tracer stepped through: fix a buy day, try every later day as the sale, and keep the largest difference. All 15 pairs are checked before the answer is certain.
Time O(n²) · Space O(1)
- 1def maxProfit(prices):
- 2 best = 0
- 3 for buy in range(len(prices)):
- 4 for sell in range(buy + 1, len(prices)):
- 5 best = max(best, prices[sell] - prices[buy])
- 6 return best
Approach 2 · Track the lowest price
Walkthrough
Same input, now one step at a time. Each frame highlights the line that runs and the values it changes.
- 1.Set
lowto the first price andbestto 0. - 2.At each price, if it is below
low, it becomes the newlow. - 3.Then try selling today:
best = max(best, price - low). A sale on the day of a new low earns 0. - 4.After the walk,
bestis the answer. If prices only fall, it stays 0.
Python
Best Time to Buy and Sell Stock
- Input:
- prices = [7, 1, 5, 3, 6, 4]
- Output:
- 5
- 1def maxProfit(prices):
- 2 low = prices[0]
- 3 best = 0
- 4 for price in prices:
- 5 if price < low:
- 6 low = price
- 7 best = max(best, price - low)
- 8 return best
Start with low at the first price and best at 0: no profit yet.
The Pattern
The pattern rests on an invariant, a fact that stays true after every step: once you have read index i, low is the cheapest price from index 0 through i, and best is the largest profit from any trade in that range. Each new price needs only those two numbers, so nothing to the left needs a second look.
From the trace
Best Time to Buy and Sell Stock
best becomes 5.Check it against the walkthrough. low dropped from 7 to 1 at prices[1] and never moved again, because no later price fell below 1. Each later day was tested once against that 1: 5 gave 4, 3 gave 2, 6 gave 5, and 4 gave 3. best changed only twice, from 0 to 4 and from 4 to 5. Six reads replaced fifteen pair checks.
low is the smallest-so-far state from the start of the lesson, and best is one more number for the answer. That shape repeats across a whole family of problems: set up the state before the loop, then at each element update the state with it and update the answer from the state. It works whenever a few numbers can summarize everything to the left. The two practice problems after this one carry a different running value through the same loop.
Complexity
TimeO(n)
SpaceO(1)
One pass over n prices with constant work per price is O(n) time. You keep two numbers, low and best, so extra space is O(1). The brute force does the same subtraction for every pair of days, about n²/2 times.
Brute force
Every pair of days
O(n²) time
O(1) space
This technique
Track the lowest price
O(n) time
O(1) space
n=100
n=1,000
n=10,000
Price comparisons on a log scale. At 10,000 days the pair check does about 5,000 times more work.
When to use this in an interview
- The obvious solution is a nested loop whose inner loop rescans everything before index
i. - Each answer depends on a summary of earlier elements: a minimum, maximum, sum, count, or best so far.
- Order is part of the rule, as in “buy before you sell” or
i < j. A left-to-right scan enforces it for free. - The prompt asks for one pass or
O(1)extra space, or the data arrives as a stream.
In production
Streaming market data
A market-data service tracks the best buy-then-sell gain for thousands of symbols while prices stream in. It cannot keep every tick to compare all pairs, and it cannot rescan a symbol's history each time a new price lands. Stream processors keep a few numbers of state per key instead, updated once per event in O(1) time and memory. The walkthrough's low and best, kept per symbol, are exactly that state.
Where this breaks
One remembered low only works when you buy and sell once. Several rises and falls need a new decision on each day.
Your turn
Solve it yourself
You have watched one running value replace a nested loop. Write it yourself on the stock problem you just traced, then apply the single-pass pattern to solve Majority Element and Maximum Subarray.
- 1Solve it
Best Time to Buy and Sell Stock
Guided · the problem you traced above
- 2Majority ElementOn your own · same pattern, no walkthrough
- 3Maximum SubarrayOn your own · same pattern, no walkthrough