Back to Study Material Data Structures and Algorithms

Two Pointer Technique

The two pointer technique is an algorithm pattern where two indices, or pointers, traverse a data structure simultaneously. The two pointers may move towar...

Two Pointer Technique

Solving Array and String Problems Efficiently with Two Indices

The two pointer technique is an algorithm pattern where two indices, or pointers, traverse a data structure simultaneously. The two pointers may move toward each other from opposite ends, move in the same direction at different speeds, or maintain a window. This technique often reduces O(n^2) brute-force solutions to O(n), making it one of the most impactful patterns to master.

The opposite-end pattern places one pointer at the leftmost index and another at the rightmost index. Both move inward based on a condition. A classic application is checking whether a sorted array contains a pair that sums to a target value T. Start with left at index 0 and right at index n minus one. If A[left] plus A[right] equals T, you found the pair. If the sum is less than T, move left rightward to increase the sum. If the sum is greater, move right leftward to decrease it. Each step either finds the answer or moves at least one pointer, so the total number of steps is at most n, giving O(n) after the O(n log n) sort.

The same-direction pattern uses two pointers that start at the same end and move forward at different rates. Removing duplicates from a sorted array in-place is a textbook example. A slow pointer tracks the position where the next unique element should be written. A fast pointer scans ahead looking for values different from the one at the slow pointer. This runs in O(n) with O(1) space.

Another same-direction application is Floyd's cycle detection algorithm, used to detect loops in linked lists. A slow pointer advances one step at a time; a fast pointer advances two steps. If a cycle exists, the fast pointer eventually laps the slow pointer and they meet.

Conditions for applying the two pointer technique: the data is usually sorted or has some ordering property, the problem asks about pairs, triplets, or subarrays with a sum or length constraint, and you want O(n) time with O(1) space.

Worked example: given a sorted array and a target sum, find all unique pairs that sum to the target. Brute force with two nested loops is O(n^2). Two pointers scanning inward solve it in O(n) with the additional benefit of naturally skipping duplicates by moving the pointer past repeated values.

Interview tip: when a problem involves pairs in a sorted array or merging sorted sequences, the two pointer technique almost always applies. Suggest it early; even if it is not the final solution, it shows pattern recognition.