twopointer

Two-pointer technique, often referred to as two pointers or twopointer, is a problem-solving pattern in algorithms where two indices traverse a data structure, typically an array or string, to compare elements or maintain a dynamic window. The pointers can move toward each other or in the same direction, depending on the problem.

Variants of the two-pointer approach include left-right pointers that begin at opposite ends and move inward on sorted data to find pairs or to remove duplicates; slow-fast pointers where one pointer advances twice for each step of the other, used to detect cycles in linked lists or to locate the middle element; and moving window pointers that expand and contract a window to satisfy a sum or length constraint.

Common problems solved with the twopointer pattern include finding pairs with a given sum in sorted arrays, removing duplicates in place, partitioning an array around a pivot, and determining the maximum-length subarrays under sum or length constraints. The technique is valued for often achieving linear time with constant extra space.

Implementation notes: the approach generally runs in O(n) time with O(1) extra space and relies on data being amenable to index-based traversal, frequently with a monotonic or sorted order. Boundary conditions and loop termination are critical to avoid infinite loops, especially when pointers converge or the window size is fixed. In linked lists, the same idea can be adapted but may require additional state or sentinel nodes.

See also: sliding window, fast and slow pointers, two-sum.