The Two-Pointer Technique
Fast recall
Quick revision
Core answer
Whether you know the forms (opposite ends, fast/slow, parallel) and that it turns O(n^2) nested loops into O(n) with O(1) space.
Using two pointers on an unsorted array for pair sum (sort first), or moving the wrong pointer.
Two pointers: two indices, O(n) time, O(1) space. Forms: opposite ends (pair sum, reverse), fast/slow (cycle, middle), parallel (merge). Needs sorted or left-right structure.
Interview-ready guide
Interview answer
The two-pointer technique keeps two positions in a sequence and moves one or both according to information gained from the current comparison. It is useful only when that movement rules out candidates safely; sorted order, opposite ends, or a maintained window often provides that property.
In sorted two-sum, the left pointer starts at the smallest value and the right pointer at the largest. If their sum equals the target, the pair is found. If the sum is too small, keeping the same left value with any smaller right value cannot help, so left moves right. If it is too large, right moves left by the symmetric argument.
For example, for [1, 3, 4, 6, 8] and target 10, 1 + 8 is 9, so left advances. 3 + 8 is 11, so right retreats. 3 + 6 is 9, so left advances again. 4 + 6 is 10, and the algorithm returns that pair.
Each pointer moves in only one direction and at most n positions, so the scan is O(n) time and O(1) extra space. If the input is not sorted, sorting first costs O(n log n), returns a changed order unless a copy is used, and requires carrying original indices when the result asks for them.
Two pointers are not a magic replacement for nested loops. Without a monotonic rule, moving one side may discard a valid pair. I would state the invariant, trace crossing and duplicate cases, and distinguish an expanding or shrinking window from pointers that simply move toward each other.
The Two-Pointer Technique
Direct Answer
Two pointers are two indices that move through one or two sequences while preserving an invariant, so the algorithm can discard impossible candidates without testing every pair. In a sorted two-sum problem, compare the values at the ends: a sum that is too small can only improve by moving the left pointer right, and a sum that is too large can only improve by moving the right pointer left. This gives O(n) scanning after any required sort.
Deep Dive & Architecture
At any step, the active search space contains pairs whose left index is at least left and whose right index is at most right. Sorted order gives the current boundary values meaning. A too-small sum eliminates every pair using the current left value, because all alternative right values are no larger.
This elimination proof is why the algorithm is linear. Although the code has a loop and evaluates pairs, it never moves a pointer backward. The total number of pointer moves is bounded by the array length rather than multiplied into all possible pairs.
Other patterns need different invariants. Same-direction pointers can compact an array or remove duplicates while one marks the read position and one the write position. A sliding window adds and removes items while maintaining a condition over a contiguous range. Calling all of them two pointers is convenient, but their movement proofs are not interchangeable.
Output requirements affect preparation. Sorting a copy is harmless when values alone are returned. Original indices require sorting value-index pairs or using a hash-based alternative. Inputs that arrive already sorted expose the strongest reason to prefer the constant-space pointer scan.
Code Example
def pair_with_sum(sorted_numbers, target)
left = 0
right = sorted_numbers.length - 1
while left < right
sum = sorted_numbers[left] + sorted_numbers[right]
return [sorted_numbers[left], sorted_numbers[right]] if sum == target
sum < target ? left += 1 : right -= 1
end
nil
end
raise unless pair_with_sum([1, 3, 4, 6, 8], 10) == [4, 6]
raise unless pair_with_sum([2, 2], 4) == [2, 2]
raise unless pair_with_sum([1, 2, 3], 20).nil?
Common Mistakes & Pitfalls
Using two pointers on an unsorted array for pair sum (sort first), or moving the wrong pointer.
Check your understanding
Answer these without looking back at the article.
- What invariant justifies moving the left pointer after a small sum?
- How do you preserve original indices if sorting is required?
- How is a sliding window different from opposite-end two pointers?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.