Lesson 2.2 · Arrays

One Pass with Running State

The single most common array technique: walk once and keep a few variables that summarise everything so far, instead of looking back.

12 min

Think of it like this

When you track your daily steps, you don't keep every number from the past year to know your best day. You keep one number, "best so far", and update it each evening. That one number replaces looking back.

1.Why looking back is the bottleneck

Many slow solutions have the shape "for each i, look at every j before i". That inner look-back is O(n), making the whole thing O(n²).

Ask: what exactly do I need from the elements before i? Usually it's one summary: the minimum so far, the maximum so far, a sum, or a count. Keep that summary in a variable, update it as you go, and the look-back disappears.

2.The template: use the summary, then update it

Order matters. At index i, first use the summary of elements 0..i−1 to compute something for i, then fold a[i] into the summary. Swapping these steps would let an element pair with itself.

MaxDifference.java

public class Main {
    // largest a[j] - a[i] with i < j
    static int maxDiff(int[] a) {
        int minSoFar = a[0], best = Integer.MIN_VALUE;
        for (int j = 1; j < a.length; j++) {
            best = Math.max(best, a[j] - minSoFar);   // use the summary of 0..j-1
            minSoFar = Math.min(minSoFar, a[j]);      // then include a[j]
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(maxDiff(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(maxDiff(new int[]{9, 7, 4}));
    }
}

Output

5
-2

Quick check

In maxDiff, what goes wrong if you update minSoFar before computing best?

3.Prefix and suffix thinking

Sometimes index i needs a summary of everything on its left and everything on its right. Do two passes: one left-to-right filling left[i], one right-to-left filling right[i], then combine. Trapping rain water and product-of-array-except-self both work this way, and you'll meet them in the Two Pointers and Prefix Sum modules.

Remember

Replace "look back at everything" with a running summary variable.
Use the summary first, then update it with the current element.
When both sides matter, compute prefix and suffix summaries in two passes.

Common mistakes

Updating the summary before using it, so an element pairs with itself.
Initialising a minimum to 0 or a maximum to 0 when values can be negative.

Command Palette

One Pass with Running State

1.Why looking back is the bottleneck

2.The template: use the summary, then update it

3.Prefix and suffix thinking