Two pointers and sliding windows

Why it matters

Brute force over all pairs or all subarrays costs O(n²) or more. Two pointers and sliding windows reach O(n) by never moving an index backwards, but only when you can prove that the candidates you skip cannot be the answer. That proof is what interviewers listen for, and it is the same reasoning you use when processing logs or metric streams with bounded memory.

Core ideas

Pattern: Two pointers. On sorted input, start i at the left end and j at the right. Looking for a pair with a given sum: if a[i] + a[j] is too small, pairing a[i] with anything at or before j is also too small, so i can advance; symmetric logic moves j. Each step eliminates a whole row or column of candidate pairs, so the scan is O(n). Container With Most Water uses the same elimination: the shorter of the two lines cannot form a larger container with any line closer to it, so discard it. 3Sum fixes one element and runs this scan on the rest after sorting, skipping equal values to avoid duplicate triples: O(n²) overall.

Read and write pointers. A slow write index and a fast read index filter in place. Move Zeroes keeps "everything before w is the non-zero output in original order". Sort Colors extends this to four regions (less, equal, unknown, greater) maintained by three indices.

Pattern: Sliding window. For contiguous subarrays or substrings:

left = 0
for right in range(n):
    add(a[right])
    while not valid():
        remove(a[left]); left += 1
    best = max(best, right - left + 1)   # [left, right] is valid here

Invariant: after the inner loop, [left, right] is the longest valid window ending at right. Both indices only move forward, so the total work is O(n) despite the nested loop. This requires validity to survive shrinking: every sub-window of a valid window must be valid. "At most k distinct characters" and "sum at most S with non-negative values" qualify; sums with negative values do not, and need prefix sums with a hash map or a monotonic deque over prefix sums instead. For "shortest valid window" problems (Minimum Size Subarray Sum, Minimum Window Substring) validity must survive growing instead, and you record the answer inside the shrinking loop while the window is still valid.

Window state. Keep only what validity needs, updated in O(1) per step: a count map plus a counter of satisfied requirements (Minimum Window Substring), last-seen positions (Longest Substring Without Repeating Characters) or a running sum. For Longest Repeating Character Replacement, the window is valid while its length minus its largest single-character count is at most k.

Fixed windows. For windows of exactly k elements, add the entering element and remove the leaving one at each step (Permutation in String, Find All Anagrams in a String).

Exactly k. "Exactly k distinct values" is not preserved by shrinking, but "at most k" is. Count windows with at most k distinct values and subtract those with at most k − 1.

Common misconceptions

• "A loop inside a loop is O(n²)." If each pointer only moves forward, there are at most 2n pointer moves in total.
• "Every subarray-sum problem is a sliding window." Windows need validity that is monotone under shrinking or growing; with negative numbers it is not, so use prefix sums.
• "Converging pointers work on unsorted data." They rely on order; sort first (paying O(n log n)) or use hashing.
• "Either pointer can move." Each move must come with an argument that the skipped candidates cannot be optimal.
• "Record the answer anywhere in the loop." Record where the invariant holds: after shrinking for longest-valid windows, inside the shrinking loop for shortest-valid ones.

How to approach it

Ask first: contiguous or not, sorted or not, can values be negative? Then state the validity condition and why it is monotone, or the elimination argument for converging pointers, before coding. Say what the window state is and how add and remove update it in O(1). Test an empty input, a window that never becomes valid, and all-equal elements. Interviewers typically ask why the scan is linear and what changes when negative numbers are allowed. Build the reflex by asking these questions on unseen problems; recalling specific question lists is not what transfers.