Algorithm patterns

Most slow code is a nested loop that asks the same question again: "is the partner somewhere in the array?", "what is the sum of this range?", "which earlier item is still waiting?". Each pattern below replaces the rescan with a small piece of state that already holds the answer. Find the cue, apply the pattern, then prove it with the invariant.