Solving One-Pass Array and String Problems with Running State

Hello! In the previous lesson, you learned to count the cost of operations inside a loop, not just the number of loops. Now you’ll use that reasoning to build a one-pass solution: visit each item once, keep a small amount of useful information, and update it as you go.

The central question is: What must you remember about everything you have already seen to make the right decision at the next item? We’ll answer it first with an array problem, then with a string problem. Both take $O(n)$ time and $O(1)$ auxiliary space.

A running state is a useful summary of the past

Suppose you need the sum of a list. You do not need to store every partial answer. A variable holding the sum so far is enough: initialize it to zero, then add each new value. This is an accumulator. A running state is the broader idea: it might hold a sum, a minimum, a current streak, or several values that work together.

Read the opening of 7.6. The Accumulator Pattern from Foundations of Python Programming for the basic initialize–iterate–update structure. The examples are simpler than our upcoming problem; pay attention to when the accumulated value changes.

For a less obvious problem, choosing the state takes more thought than writing the loop. A useful design routine is:

1. Say precisely what each state variable means after processing an item.
2. Choose initial values that make those meanings true before or at the first item.
3. Update the variables using only their old values and the current item.
4. Check that the final state contains the requested answer.

The next example shows why a running state may need two variables rather than one.

One pass over prices: remember the cheapest earlier value

Given a list of prices in time order, find the greatest profit from buying once and selling on a later day. If no profitable trade exists, return zero. For example, [7, 1, 5, 3, 6, 4] has answer $5$: buy at $1$ and sell later at $6$.

You could inspect every possible buy–sell pair, but that takes $O(n^2)$ time. Instead, imagine the current price is today’s selling price. To calculate the best profit from selling today, you need only the lowest price on an earlier day. You do not need the entire price history.

Greg Hogg’s Best Time to Buy and Sell Stock illustrates this choice of state and its Python implementation. Watch the problem setup and the one-pass explanation; you can skip the detailed brute-force walkthrough between them.

Here is a version that makes the time-order rule explicit:

def max_profit(prices):
    cheapest_earlier = float("inf")
    best_profit = 0

    for price in prices:
        # Treat today's price as a possible selling price.
        best_profit = max(best_profit, price - cheapest_earlier)

        # Today's price can be a buying price for a later day.
        cheapest_earlier = min(cheapest_earlier, price)

    return best_profit

The order of the two updates matters to the explanation. When calculating price - cheapest_earlier, the minimum comes strictly from earlier days. Only afterward can today’s price become the cheapest buying option for a future sale.

Initially, cheapest_earlier is infinity because no earlier price exists. On the first iteration, the proposed profit is negative infinity, so best_profit stays at zero; then the first price becomes the cheapest seen. The same initialization makes an empty list return zero. If the problem instead guarantees at least one price, the empty case simply will not arise.

Trace the sample to see what the state retains:

After processing any price, cheapest_earlier holds the minimum of all prices processed so far. Meanwhile, best_profit holds the best valid profit found among days processed so far, or zero if none was positive. Those statements remain true on each iteration: today is evaluated using the earlier minimum, the best answer is updated if necessary, and then the minimum is updated for future days.

This also explains two important boundaries. With decreasing prices such as [9, 7, 4], every valid proposed profit is negative, so the answer remains zero. With a cheaper price appearing after a high price, the algorithm never uses that later low price to justify an earlier sale.

The loop visits each of $n$ prices once and performs constant work per visit: $O(n)$ time. It stores only two running values: $O(1)$ auxiliary space. In particular, it creates no slice or new list.

The same design works on a string

Now consider a different task: find the length of the longest run of identical, consecutive characters. In "abbba", the longest run is "bbb", so the answer is $3$. A run must be consecutive; three occurrences scattered across a string would not count.

At each character, two facts are sufficient:

• run_length: the length of the identical-character run ending here;
• best_length: the longest run found anywhere so far.

To update run_length, you also need to remember the previous character. If the new character matches it, extend the run. Otherwise, a new run of length one begins.

def longest_run(text):
    previous = None
    run_length = 0
    best_length = 0

    for char in text:
        if char == previous:
            run_length += 1
        else:
            run_length = 1

        previous = char
        best_length = max(best_length, run_length)

    return best_length

For "abbba", the successive run_length values are $1,1,2,3,1$. The last a ends the current "bbb" run, but it does not erase best_length, which remains $3$. For an empty string, the loop does not run and the answer is $0$.

Notice the distinction between a current candidate and the best answer so far. The current candidate can shrink or restart; the best answer must preserve a result that was found earlier. This string solution, like the price solution, uses $O(n)$ time and $O(1)$ auxiliary space.

The supplied image previews another array problem with the same two-state distinction. At index $1$, the contiguous sum ending at the current element is $2+3=5$, and the best sum found so far is also $5$.

Those two values happen to agree at this point in the picture. As with run_length and best_length, they have different jobs: one describes a candidate tied to the current position, while the other preserves the overall result. You’ll develop the full maximum-subarray update later in the course.

Key takeaways

A one-pass algorithm succeeds when its running state retains exactly the information needed for the next item. Define what each variable means, initialize it carefully, update it in an order that respects the problem’s rules, and keep the best answer separately when a current candidate can change. Both examples here replace a history of values with a few variables while still producing the correct result.

Next, you’ll tackle lookup and pair-finding problems. Those also process items as they arrive, but when a few variables cannot summarize the necessary history, a dictionary or set can retain the specific values you need.