Walk a sequence from both ends (or at two speeds) to find pairs and partitions without a second nested loop.
What the two pointers pattern is
Two pointers means maintaining two indexes into a sequence and moving them according to a rule, so that a search over pairs - which naively costs O(n²) - happens in a single O(n) pass. The power comes from a discard argument: at every step, the comparison at the current pointers lets you eliminate all pairs involving one of the pointed-at elements, so you never have to look at them.
The two dominant shapes are converging pointers (start at both ends, move toward each other - pair-sum problems, palindrome checks, container-with-most-water) and parallel pointers (both start at the left and move rightward at different paces - deduplication, partitioning, merging two sorted arrays). The sliding window is really a special case of parallel pointers where the two indexes bound a contiguous range.
How to recognize it
Signals: the input is sorted (or you are allowed to sort it), the question asks about pairs or triplets meeting a condition ('two numbers that sum to target'), or the task is in-place rearrangement - remove duplicates, move zeroes, partition around a pivot. Palindrome questions are converging pointers by their very shape.
The key question to ask yourself: 'if I compare the elements at my two pointers, can I definitively rule out one of them from all future consideration?' If yes, two pointers gives you O(n). If a comparison tells you nothing certain - typical with unsorted data - you need sorting first, a hash map instead, or a different pattern.
Why sorted input unlocks the discard argument
Take 'find two numbers summing to target' in a sorted array with pointers at both ends. If the current sum is too small, no pair involving the left element can ever work - everything the left element could be paired with is at most the current right element, and that sum was already too small. So left++ discards n−1 candidate pairs in one move. If the sum is too big, the mirror argument discards the right element. Every step eliminates one element for good, so the scan is linear and provably misses nothing.
This is the reasoning interviewers actually probe for. Being able to say why moving the pointer is safe - not just that the template says so - is the difference between recall and understanding.
pseudocode
left = 0, right = n - 1
while left < right:
sum = a[left] + a[right]
if sum == target: return (left, right)
if sum < target: left += 1 # a[left] can pair with nothing bigger
else: right -= 1 # a[right] can pair with nothing smaller
return not found
Complexity
Converging pointers touch each element at most once: O(n) time, O(1) extra space. Parallel-pointer partitioning and deduplication are also O(n)/O(1). When you must sort first, the sort's O(n log n) dominates - still far better than the O(n²) pair scan, and the O(1) space often beats the hash-map alternative.
Common pitfalls
Applying converging pair-sum pointers to an unsorted array - the discard argument silently evaporates and the answer is just wrong. Sort first, or use a hash map.
Sorting when the problem asks for original indexes: sorting destroys them. Either return values, sort index pairs, or switch to a hash map.
Loop condition: left < right for pairs (an element cannot pair with itself); crossing conditions differ for partitioning variants. Decide deliberately, not by habit.
In deduplication/partition problems, confusing the 'write' pointer with the 'read' pointer - name them write and read, not i and j, and the bug disappears.
Forgetting to skip duplicates in 3-sum style problems, producing repeated triplets in the output.
Worked examples
1. Pair with target sum in a sorted arrayeasy
Given a sorted array and a target, return the indexes of two distinct elements that sum to the target.
Brute force checks all pairs: O(n²). A hash map gets O(n) time but O(n) space. The array being sorted hints there is an O(1)-space route.
Point left at the smallest element and right at the largest. Their sum can be adjusted in a controlled direction: increasing left raises it, decreasing right lowers it.
If the sum is too small, no partner for a[left] exists anywhere (a[right] was its best shot) - discard left. If too big, discard right. Repeat.
Each iteration permanently removes one element from consideration, so at most n−1 iterations. O(n) time, O(1) space.
pseudocode
left = 0, right = n - 1
while left < right:
sum = a[left] + a[right]
if sum == target: return (left, right)
else if sum < target: left += 1
else: right -= 1
Remember: Sorted order turns one comparison into a proof that discards an entire element's worth of pairs.
2. Remove duplicates from a sorted array in placeeasy
Given a sorted array, remove the duplicates in place so each value appears once, and return the new length.
Because the array is sorted, duplicates sit next to each other - a value is a duplicate exactly when it equals its predecessor.
Use parallel pointers with distinct jobs: read scans every element; write marks the end of the deduplicated prefix. The invariant: a[0..write−1] is the final answer so far.
For each read element, if it differs from a[write−1], keep it: copy to a[write] and advance write. Otherwise skip it.
One pass, O(n) time, O(1) space, and the invariant makes correctness self-evident.
pseudocode
if n == 0: return 0
write = 1
for read in 1 .. n-1:
if a[read] != a[write - 1]:
a[write] = a[read]
write += 1
return write
Remember: Parallel pointers = a fast read head and a slow write head; the write prefix is always the finished answer.
3. Container with most watermedium
Given heights of n vertical lines, choose two that, with the x-axis, form a container holding the most water. Area = min(height[i], height[j]) × (j − i).
All pairs is O(n²). Start pointers at both ends - the widest possible container - and ask which pointer can safely move inward.
The area is limited by the shorter line. Moving the taller line inward can never help: width shrinks and the height limit stays capped by the same shorter line. Moving the shorter line is the only move with upside.
So: compute the area, record the best, and always advance the pointer at the shorter line.
Every element is discarded exactly once with a proof that no better container involving it remains - O(n) with no answer missed.
pseudocode
left = 0, right = n - 1, best = 0
while left < right:
best = max(best, min(h[left], h[right]) * (right - left))
if h[left] < h[right]: left += 1
else: right -= 1
return best
Remember: Move the pointer at the limiting (shorter) side - the only move that could possibly improve the answer.
4. 3-sum: all unique triplets summing to zeromedium
Given an integer array, return every unique triplet (a, b, c) with a + b + c = 0.
Sort the array - O(n log n) buys us both the pair-sum discard argument and adjacent duplicates that are easy to skip.
Fix the smallest element of the triplet by index i. The remainder is exactly the pair-sum problem: find two elements to the right of i summing to −a[i], with converging pointers.
Skip duplicate values of a[i] (if a[i] equals a[i−1], every triplet starting here was already produced). After finding a match, advance both pointers past any repeated values for the same reason.
n choices of i, each with an O(n) pair scan: O(n²) total - optimal for enumerating all triplets - and O(1) extra space beyond the output.
pseudocode
sort(a)
for i in 0 .. n-3:
if i > 0 and a[i] == a[i-1]: continue
left = i + 1, right = n - 1
while left < right:
s = a[i] + a[left] + a[right]
if s < 0: left += 1
else if s > 0: right -= 1
else:
record (a[i], a[left], a[right])
left += 1; right -= 1
skip duplicates of a[left-1] and a[right+1]
Remember: Reduce k-sum to (k−1)-sum by fixing one element - 3-sum is just a loop wrapped around the pair-sum pattern.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1Converging two pointers find a pair summing to a target in O(n). What property of the input makes the pointer moves safe?
The array contains no duplicates
✓ The array is sorted, so each comparison rules out every remaining pair involving one endpoint
The array has an even number of elements
All elements are positive
Sorted order is what turns 'sum too small' into a proof that the left element pairs with nothing - its best possible partner was already tried. Without sorting, a comparison proves nothing and the technique breaks.
2In container-with-most-water, why is the pointer at the taller line never moved?
Moving it would make the array unsorted
✓ The width shrinks and the min-height cap stays the same or gets worse, so no improvement is possible
The taller line always forms the final answer
To keep the loop O(n log n)
Area = min(heights) × width. Moving the taller pointer keeps the same limiting height (or worse) while strictly shrinking the width - provably never better, so those pairs can be skipped wholesale.
3You need the original indexes of the two elements that sum to a target, and the input is unsorted. Best approach?
Sort, then use converging pointers
✓ Use a hash map of value → index in one pass
Use parallel pointers without sorting
Binary search for each element's complement
Sorting destroys the original indexes. A hash map finds each element's complement in O(1) while preserving positions - O(n) time, O(n) space is the right trade here.
4In the in-place deduplication problem, what is the loop invariant that makes the algorithm correct?
The read pointer is always ahead of the write pointer
✓ Everything before the write pointer is the correct, duplicate-free answer so far
The array remains sorted after every swap
The write pointer only moves when the read pointer does not
The write-prefix invariant - a[0..write−1] is exactly the deduplicated output - holds before and after every step. Stating an invariant like this is also the cleanest way to explain your code in an interview.
5How does 3-sum use the two pointers pattern?
It runs three pointers converging simultaneously
✓ It sorts, fixes one element, and solves the remaining pair-sum with converging pointers
It uses two hash maps instead of pointers
It doesn't - 3-sum requires dynamic programming
Fixing the first element reduces 3-sum to 2-sum on the suffix, solved with converging pointers in O(n). The outer loop makes it O(n²) overall, with duplicate-skipping to keep triplets unique.
Frequently asked questions
When do I use two pointers instead of a hash map for pair problems?
Use two pointers when the array is sorted (or sorting is acceptable) and you want O(1) extra space. Use a hash map when the input must stay unsorted - for example when the answer needs original indexes - accepting O(n) space.
What is the difference between two pointers and sliding window?
A sliding window is a special case of parallel two pointers where the two indexes always bound one contiguous range and the state describes everything inside it. General two-pointer problems - converging ends, read/write partitioning, merging - carry no such range semantics.
Does two pointers only work on sorted arrays?
No. Converging pair-sum arguments need sorted input, but parallel-pointer techniques - in-place deduplication, partitioning, moving zeroes, merging - rely on position, not order, and work on any array.
How do I explain the correctness of a two-pointer solution in an interview?
State the discard argument: every pointer move is justified by a proof that the skipped pairs cannot contain the answer. For pair-sum: 'if the sum is too small, the left element's best partner already failed, so it can never succeed - discard it.'