On this page
Description
Single-pass state tracking walks an array once while remembering a small summary of everything before the current element: the lowest price so far, or the length of the current streak. Each new element is judged against that summary. It's how Best Time to Buy and Sell Stock and Max Consecutive Ones run in O(n) time with O(1) space. It's also the first step toward the state-machine DP problems that come later.
We'll go from simple to more technical:
- The pattern: use the state from before this element, then update it.
- A second flavor: state that includes the current element (streaks).
- Where running best-so-far values show up in production.
- When one number isn't enough, and how a few numbers can be.
The approach
To find the best profit from one buy and a later sell, you could try every pair of days. That's O(n^2). But to judge selling today, you only need one fact about the past: the lowest price before today. So keep that one number. Each day, first work out the profit of selling today at the lowest earlier price. Then let today's price update the lowest price.
For prices [8, 5, 9, 3, 6, 4]:
| Day's price | Lowest price before today | Profit if sold today | Best profit | Lowest price after today |
|---|---|---|---|---|
| 8 | none | 0 | 8 | |
| 5 | 8 | -3 | 0 | 5 |
| 9 | 5 | 4 | 4 | 5 |
| 3 | 5 | -2 | 4 | 3 |
| 6 | 3 | 3 | 4 | 3 |
| 4 | 3 | 1 | 4 | 3 |
The best is 4: buy at 5, sell at 9. The later low of 3 never finds a high enough price after it.
Java
int minPrice = Integer.MAX_VALUE, best = 0;
for (int price : prices) {
best = Math.max(best, price - minPrice); // sell today, bought at the lowest price BEFORE today
minPrice = Math.min(minPrice, price); // only then may today count as a buying day
}
Python
min_price, best = float("inf"), 0
for price in prices:
best = max(best, price - min_price) # sell today, bought at the lowest price BEFORE today
min_price = min(min_price, price) # only then may today count as a buying day
The order matters. The answer for today uses the state from strictly before today. Only then does today's price join the state for the days after it.
A second flavor: state that includes today
Some problems need today inside the state. Max Consecutive Ones counts the current streak of 1s, including the current element, and then compares it with the best streak:
Java
int streak = 0, maxStreak = 0;
for (int num : nums) {
streak = (num == 1) ? streak + 1 : 0; // update FIRST - today's element is part of this streak
maxStreak = Math.max(maxStreak, streak);
}
Python
streak = max_streak = 0
for num in nums:
streak = streak + 1 if num == 1 else 0 # update FIRST - today's element is part of this streak
max_streak = max(max_streak, streak)
Here the order is reversed. A streak that didn't count today's value wouldn't measure "consecutive ones up to here". So ask: is the current element a candidate compared with everything before it, like a sell price? Then use the old state first. Is it part of what you're measuring, like a streak? Then update first.
Where you'll see it
A running best-so-far value lets each new observation be judged in O(1), without replaying history. Think of the lowest latency seen in this window, or the cheapest quote so far in a stream of bids.
Which tool for which job?
| You need | Use |
|---|---|
| Best later-minus-earlier difference | the lowest value so far, used before updating |
| The longest run of something | a current streak and a best streak |
| Up to two trades, a cooldown or a fee | a few states updated together (a small state machine) |
| The second largest | two running values |
| A value that appears more than n/2 times | Boyer-Moore voting, then verify |
| Answers that depend on the whole history | more state, or another structure |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Updating the state before using it | an element plays both roles (buy and sell the same day) | compute the answer first, then update |
| Updating several states one after another | later states see this step's new values | update them together from the old values |
| Starting the minimum at 0 | every price looks like a loss | start at +inf or the first element |
| Forgetting the last streak | a run that reaches the end isn't counted | compare after updating, or once more after the loop |
| Trusting Boyer-Moore without a check | a "majority" that isn't one | count the candidate in a second pass |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. A solution updates the lowest price with today's price before computing today's profit. What goes wrong?
Show answer
The same day can be both the buy day and the sell day, for a "profit" of 0. In the classic version that's hidden, because 0 is already allowed as the answer. When a trade is required and a loss is possible, it reports 0 on falling prices instead of the smallest loss.
2. Max Consecutive Ones updates its streak first. Buy and sell computes its answer first. What decides the order?
Show answer
The current element's role. A candidate, like a sell price judged against earlier buy prices, uses the old state first. A part of what's being measured, like a streak that includes today, updates first.
3. Someone extends the one-trade solution to "at most two trades" with the same two variables. What's missing?
Show answer
One running minimum can't describe "the best result after zero, one or two finished trades" all at once. Two trades need several states tracked side by side, a small DP, not the same loop run twice.
Key takeaways
- Keep one running summary of the past and use it in O(1), instead of rescanning history for each element.
- Use the old state first when the current element is a candidate. Update first when it's part of the state, like a streak.
- One number works only when the answer depends on one summary of the past. Problems that need more need more state.
- Several states must be updated together, from the old values.