Overview
The Two-Pointer Technique is an algorithmic approach in which two pointers move through an array, string, linked list, or other sequence according to specific conditions. The pointers may move toward each other, in the same direction, or at different speeds.
How it works
Identify the sequence and the condition that must be checked.; Choose suitable starting positions for the two pointers.; Compare the values or positions referenced by the pointers.; Move one or both pointers according to the problem's rules.; Continue until the required condition is satisfied or the pointers meet or cross.
Key concepts
Pointer positions; Opposite-direction traversal; Same-direction traversal; Sorted sequences; Boundary movement; Invariant maintenance
Time complexity
operation: Single traversal with two pointers; complexity: O(n); operation: Nested pointer movement; complexity: Often O(n) when each pointer moves only forward or backward a limited number of times
Space complexity
Usually O(1) auxiliary space when pointers are used directly without additional collections.
Example
array: 1; 2; target: 14; problem: Find two numbers whose sum equals 14.; steps: Start with left = 0 and right = 5.; 1 + 10 = 11, which is smaller than 14, so move left forward.; result: 4; 10
Applications
Two Sum in sorted arrays; Palindrome checking; Removing duplicates; Merging sorted arrays; Partitioning sequences; Container With Most Water