Two Pointers

Picture a sorted shelf of numbered books with one hand at each end. If the two books together are too heavy (their sum is too big), move the right hand inward to a lighter book; if too light, move the left hand inward. You close in from both sides and check far fewer pairs than trying every combination - and you carry nothing extra in your pockets.

Example: sorted [1, 3, 4, 7], looking for a pair that sums to 8. Left = 1, right = 7, and 1 + 7 = 8 - found right away. If the target were 9, the 1 + 7 = 8 is too small, so move the left hand up to 3; 3 + 7 = 10 is too big, so move the right hand down - never re-checking pairs you've already ruled out.

"Two pointers" is an umbrella over three distinct movements. Identifying which one you need is most of the battle.

The core advantage across all three: you replace a remembered set of candidates (a hash map) with the structure of the data, so extra space drops to O(1).

On a sorted array, set left = 0, right = n-1. Compare the current sum to the target: if it's too small, the only way to grow it is to move left right (toward bigger values); if too big, move right left. Each step eliminates one element, so it's a single O(n) pass.

Two pointers starting together, fast advancing two steps for every one of slow. After the loop, slow sits at the middle (fast reaches the end at twice the speed). If there is a cycle, fast eventually laps slow and they meet — that meeting is impossible without a loop, which is the whole proof.

To find the cycle's start: after they meet, reset one pointer to the head and advance both one step at a time; they meet again exactly at the cycle entrance.

For in-place transformations, keep a slow write pointer marking the next slot to fill and a fast read pointer scanning every element. Copy only the elements that should be kept; write ends up as the new length. This is how you remove duplicates from a sorted array or move all zeroes to the end — in O(n) time, O(1) space.

Three-sum is the canonical "two pointers inside a loop" problem. Sort first. Then fix each element a[i] and run an opposite-ends two-pointer scan on the remainder for the pair that sums to -a[i]. Skip duplicate values of both the fixed element and the moving pointers to avoid repeated triplets. Total cost: O(n) per fixed element × n elements = O(n²), which beats the O(n³) brute force.