Two Pointers
Two indices moving through a sequence — from opposite ends or in lockstep — to cut brute-force O(n²) scans to O(n).
Try answering in your head first, then click a question to check the model answer.
Q1.Walk through the two-pointer approach for finding a pair in a sorted array that sums to a target value.(show answer)
Start with low at the beginning and high at the end. If arr[low] + arr[high] equals the target, you're done. If the sum is too small, move low up (since the array is sorted, this can only increase the sum). If too large, move high down. This guarantees each pointer moves at most n times total, giving O(n) time instead of the O(n²) brute-force check of every pair.
Q2.Why does sortedness matter for the "opposite ends closing in" two-pointer pattern to work correctly?(show answer)
The algorithm's correctness relies on knowing that moving low up strictly increases the sum, and moving high down strictly decreases it — a guarantee that only holds if the array is sorted. On an unsorted array, moving either pointer could move the sum in either direction, so there'd be no principled way to decide which pointer to move next.
Q3.How does the fast/slow pointer technique find the middle of a linked list in one pass?(show answer)
Both pointers start at the head; each step, the slow pointer advances one node and the fast pointer advances two. When the fast pointer reaches the end of the list, the slow pointer — having moved half as far — is at the middle. This avoids a first pass to count the list's length and a second pass to walk to the midpoint.
Q4.Give an example of a two-pointer variant that isn't the classic "opposite ends" pattern.(show answer)
The "read/write" pointer pattern used for in-place array modification — e.g. removing duplicates from a sorted array. A "write" pointer marks where the next unique element should go; a "read" pointer scans ahead, and whenever it finds a new unique value, that value is copied to the write pointer's position and the write pointer advances. Both pointers move in the same direction, unlike the opposite-ends pattern.