Array Traversal
Read each value once while carrying only the state needed for the answer.
- Recognition signals
- every element matters · one pass is possible
- Common invariant
- After index i, the stored state correctly describes the processed prefix from 0 through i.
- Expected complexity
- Usually O(n) time
