Two pointers and sliding window

In short: Two pointers and sliding window are patterns that let many tasks on lists be solved in one pass (O(n)) instead of nested loops (O(n²)).

In more detail: With two pointers, two indices run through the list, for example towards each other from both ends. With a sliding window, a range grows and shrinks over the list, and you maintain the sum or count inside the window.

In Depth

• Two-pointer example: In a sorted list, find two numbers that add up to a sum: start at left and right, if the sum is too large decrease right, if too small increase left.
• Window example: longest substring without repeats: expand the window, shorten from the left on a repeat.
• Checking a palindrome: pointers at both ends, running inwards.
• Requirement: often sorted data or tasks with contiguous sections.
• Running time: Each pointer passes through the list at most once: O(n).

See also: Big O notation, Arrays