Array Scans

Tactic

Array scans turn a sequence into a stream of decisions. The move is to walk left to right or right to left once, carrying the smallest piece of state that makes the next item meaningful.

The invariant is the summary of everything already seen. That summary might be a best value, a running count, a last position, a candidate answer, or a flag. If the summary is enough to answer the next step, a nested loop is probably unnecessary.

Design the scan by saying what the state means before reading nums[i], then update the answer and state in a fixed order. Many bugs come from updating the state before the answer when the current element is not supposed to compare with itself.

Value

A scan is valuable because it replaces repeated re-reading with one controlled pass. It is often the first simplification before a more named tactic appears: prefix sums are scans with checkpoints, greedy reachability is a scan with a frontier, and Kadane-style DP is a scan with a compressed state.

Direct complexity example

Brute force: Check every start and end pair for a property: $O(n^2)$ time and $O(1)$ extra space.
With this tactic: Carry the needed summary while reading each value once: $O(n)$ time and usually $O(1)$ extra space.
Space: If the summary is a frequency table or set, the scan may spend $O(k)$ space for the distinct values it needs to remember.

Challenges this solves

maximum or minimum so far
first or last occurrence tracking
one-pass profit and reachability
counting events while preserving order

When to use it

Use this tactic when these conditions are true:

the answer depends on a prefix, suffix, or best-so-far value
each element only needs information from one side
the input order matters and sorting would destroy the meaning
the brute force repeats the same prefix or suffix work

When not to use it

Reach for a different tactic when these warning signs appear:

a future item can invalidate many earlier choices in a way the state cannot summarize
the problem asks for arbitrary range queries many times and needs preprocessing
the needed state grows into all previous pairs or all previous subarrays

Terminology clues

These prompt words often point toward this concept:

single pass
in one traversal
maximum so far
running
previous
last seen
best profit
left to right