Single-Pass Optimization (one scan, streaming state)

Single-pass algorithms stream data once—O(n) time, O(1) extra space for many frequency or parity tasks. Multiple passes may be unnecessary if you carry the right running state.

Why this shows up in the real world

Sensor pipelines cannot rewind terabytes. Payment streams detect fraud in one scan.

Core idea (explained for students)

Replace two-pointer or sort-first approaches with one scan when monotonicity allows: Dutch flag, majority element Boyer–Moore, running max/min.

Try this in Python

def boyer_moore_majority(a: list[int]) -> int | None:
    cand, cnt = None, 0
    for x in a:
        if cnt == 0:
            cand, cnt = x, 1
        else:
            cnt += 1 if x == cand else -1
    return cand if a.count(cand) > len(a) // 2 else None


print(boyer_moore_majority([2, 2, 1, 1, 1, 2, 2]))

Common mistakes

• Needing random access while pretending to stream—sometimes you must buffer.
• Integer overflow in rolling aggregates.

Key takeaways

• Ask: Is a second pass only for sorting? Maybe counting sort buckets suffice.
• Track extremes with tuples (best_val, best_idx) in one walk.