Two Pointers

Array and String Patterns · 25 min

DSA · Arrays · Pattern

Two pointers: a nested loop collapsed into one pass

On a sorted array, one index at each end and a single rule about the sum find a target pair in one sweep. You will trace it by hand on 1 3 4 6 8, then step it against the brute-force loop.

Walk the pointers step by step →
nested loop · 8 checks
→
two pointers · 4 checks

01 The idea

Two indices walking toward each other

You are given a sorted array and a target. The obvious plan is to try every pair: a loop inside a loop. It works, but on a list of 1000 numbers that is roughly half a million checks, and the cost grows as the square of the length.

The two-pointer plan looks at one pair only. Put L on the first element and R on the last, add them, and compare that sum with the target. Whatever the answer is, you learn enough to throw one element away for good. The array is sorted, so a[L] is the smallest value still in play and a[R] is the largest. A sum that falls short can only be rescued by a bigger left value. A sum that overshoots can only be saved by a smaller right value.

Sum too small? The left value is too small for anybody — move L right. Sum too big? The right value is too big for anybody — move R left. Sum equal? You are done.
SortedThe array is in ascending order, so index 0 holds the smallest value and index n−1 the largest. Two pointers depends on this and returns wrong answers without it.
PointerHere it means an array index, not a C pointer. L starts at 0, R starts at n−1, and each one only ever moves in its own direction.
WindowThe stretch of array still in play, from L to R. Every comparison shrinks it by one element, which is why the walk always ends.

02 Hand trace

Find a pair summing to 10 in 1 3 4 6 8

The array is 1 3 4 6 8 and the target is 10. L starts at index 0 (value 1), R starts at index 4 (value 8). The two rose cells are the pair being added on that row. Check every sum yourself before you read the note beside it.

L=0 R=4134681+8 = 9 < 10 → drop 1, L++
L=1 R=4134683+8 = 11 > 10 → drop 8, R--
L=1 R=3134683+6 = 9 < 10 → drop 3, L++
L=2 R=3134684+6 = 10 → found, indexes 2 and 3

Four comparisons. The nested loop needs eight on this exact list, and ten if the pair had not existed at all. Look at what each row bought you: row one did not merely fail, it proved that the value 1 can never reach 10 with any partner, because 8 was already the biggest partner on offer. One comparison, one element eliminated forever — that is the whole pattern.

Had the target been 9 instead, the first look at 1 and 8 would have landed straight away. That is the lucky case, not the lesson. The lesson is what you do when the first look misses.

03 The code

From two loops to one walk

Both versions answer the same question and return the same pair. The difference is what happens after a failed comparison: the nested loop learns nothing, while the walk removes a candidate from the problem.

Naive · nested loop

for i = 0 to n-2:    for j = i+1 to n-1:        if a[i] + a[j] == target:            return (i, j)return "no pair"

Improved · two pointers

L = 0;  R = n - 1while L < R:    s = a[L] + a[R]    if s == target:  return (L, R)    if s <  target:  L = L + 1    else:            R = R - 1return "no pair"

Sorted input became a requirement, not a detail. The nested loop runs on any order at all. The walk reads a[L] as the smallest live value and a[R] as the largest, and that sentence is only true on a sorted array. Hand the improved version an unsorted list and it will report "no pair" for inputs that have one.

One index moves per comparison, instead of a whole inner loop finishing. In row 1 of the trace, 1 + 8 = 9 fell short and index 0 was gone. The nested loop had to pair 1 with all four partners before it gave up on 1, and even then it knew nothing about 3.

The loop condition is now while L < R. L only rises and R only falls, so the window loses exactly one element per comparison. That is the proof the walk terminates, and the proof that it runs at most n-1 comparisons.

05 Cheat sheet

The numbers you will be asked for

CaseCostWhy
Two pointers, best caseO(1)The pair sits at the two ends, so the first comparison lands. Target 9 on 1 3 4 6 8 does exactly this.
Two pointers, average and worstO(n)Each comparison moves L up or R down, so at most n-1 of them happen before the pointers meet.
Extra spaceO(1)Two integer indices. Nothing is copied and nothing is allocated.
Input not sorted yetO(n log n)The sort dominates the linear scan that follows it.
Nested loop, worst caseO(n²)All n(n-1)/2 pairs get checked. That is 10 pairs at n=5 and 4950 at n=100.
Needs sorted inputThe only precondition, and the only thing that can silently produce a wrong answer.
In placeConstant extra memory, which is what separates it from the hash-set solution.
Never backtracksL only rises and R only falls, so no index is ever visited twice.

06 Where & why

When two pointers is the right answer

Two pointers is not a general search tool. Its value is narrow and specific: it turns a nested loop into one pass, but only when the data is ordered in a way that lets a failed comparison eliminate a candidate. Without that ordering, the pattern does not apply at all.

Reach for it when…

The array is already sortedOr you needed it sorted anyway for another reason, so the sort is not a cost you are adding.
The condition moves in one directionSum, difference, or area — anything where moving a pointer changes the value predictably.
Memory is the constraintTwo indices instead of a hash set that can hold up to n keys.
You need every matching pairThe walk emits them in order for the cost of one pass — as long as you skip repeated values on a match, or duplicates will re-emit the same pair.

Use something else when…

SituationBetter choiceWhy
The input is unsorted and you need one answerHash set, one passO(n) time without paying O(n log n) to sort. It costs O(n) memory in exchange.
You must return the original indexes, as in LeetCode Two SumHash map, value → indexSorting destroys the original positions. Pairing each value with its index before sorting also works, but the hash map is shorter.
The condition is not monotone, for example a[i] XOR a[j] == kHash map or a bit trieMoving a pointer no longer changes the result in a known direction, so the discard rule is simply invalid.
Data arrives as an unbounded streamHash map with countsYou cannot sort what has not arrived yet, and the walk needs both ends up front.
Two pointers is a habit, not a single trick. Whenever you write a nested loop over an ordered structure, ask whether one comparison can rule out one candidate for good. If it can, the inner loop was never necessary — and that question is what the interviewer is really testing.

07 Interview questions

Answers you can say out loud in twenty seconds

These run in the order an interview usually escalates: what it is, why the discard rule is safe, what it costs, then the alternatives and the edge cases.

What is the two-pointer technique?
Two indices walk a sequence, usually one from each end, and every comparison lets you discard one of the two elements they point at for good. On a sorted array it replaces a nested loop with a single pass, because a failed comparison rules out a whole element rather than just one pair.
Why does moving L right increase the sum and moving R left decrease it?
Because the array is sorted ascending. a[L+1] is at least a[L], so the sum can only rise or stay the same; a[R-1] is at most a[R], so the sum can only fall. That one-way behaviour is the entire engine — on an unsorted array neither statement holds and the method breaks.
The sum is too small. Why is it safe to throw away a[L] completely?
Because a[R] is the biggest partner a[L] will ever get. If a[L] + a[R] is already below the target, then a[L] with any other live element is smaller still. So no pair containing a[L] can reach the target, and dropping it loses nothing.
What is the time complexity, and why exactly?
O(n) on an already-sorted array. Every comparison either returns or moves L up by one or R down by one, and the two only ever move toward each other. The gap starts at n-1 and shrinks by one each time, so there are at most n-1 comparisons.
What is the space complexity?
O(1) — two integer indices and nothing else. That is the main reason to prefer it over the hash-set solution, which needs O(n) memory for the same O(n) time.
What if the array is not sorted?
Then you pay O(n log n) to sort it first, and the sort dominates the linear walk. At that point a hash set is usually the better answer at O(n) time, unless memory is tight or you needed the sorted order for something else anyway.
Two pointers or a hash table for two-sum?
Hash map from value to index: O(n) expected time, O(n) space, works on unsorted input, and keeps the original indexes. Two pointers: O(n) time, O(1) space, needs sorted input, and sorting destroys the original indexes. Choose by whether the input is already sorted and whether memory matters.
How do you return every pair that hits the target, not just the first?
On a match, record the pair and then move both pointers inward together. Also skip any repeat of the value you just consumed on each side, otherwise duplicate values emit the same pair twice. Moving only one pointer would immediately re-find the pair you just took.
What happens if L and R meet without finding anything?
You return not-found. The loop condition is while L < R, so it ends the moment they touch. Nothing was missed, because each index was proved impossible at the moment it was dropped — that argument is what makes the early discards correct.
Does it still work with duplicate or negative values?
Yes on both counts. The rule only needs the array to be sorted; it never assumes the values are distinct or positive. Duplicates matter only when you are listing all pairs, where you must skip repeated values so the same pair is not emitted twice.
Where does this pattern actually show up?
Pair-sum on sorted input, three-sum (fix one element and two-pointer the rest), container with most water, palindrome checks, merging two sorted arrays, and removing duplicates in place. Interviewers reach for it because it tests whether you can spot a nested loop that never needed to be nested.
Would you ever ship the nested loop instead?
Almost never for this problem — it is O(n²) and a linear alternative always exists. It is still worth writing once as a reference implementation, so you can check the fast version against it on small random inputs.

08 Practice problems

Six problems, in rising order

Every one is solvable with the rule from section 01 and nothing else. Before you write any code, say the discard argument out loud: which element does a failed comparison eliminate, and why.

Pair with a given difference

Easy
Given a sorted array and a value k, return true if some pair of elements differs by exactly k.
Follow-up
Both pointers start at the left and move in the same direction, not inward from the two ends. The discard rule flips: a difference that is too small means the far pointer must advance.
Show the hint
Keep a near index and a far index; if the gap is too small move the far one forward, if it is too big move the near one forward.

Palindrome check

Easy
Given a string of lowercase letters, return true if it reads the same forwards and backwards, using O(1) extra memory.
Follow-up
There is no target to compare a sum against. The pointers still start at the two ends, but the stop condition is them meeting, and a single mismatch ends it immediately.
Show the hint
Compare the characters at L and R, then step both inward in the same move rather than choosing one.

Closest pair sum

Medium
Given a sorted array and a target, return the pair whose sum is closest to the target.
Follow-up
There is no failure to discard on, so every comparison now has to be recorded rather than thrown away: the walk runs until the pointers meet, carrying the best distance seen so far. The move rule is unchanged — only the bookkeeping is new.
Show the hint
Track the smallest absolute difference so far and update it on every comparison, then move exactly as before.

Count pairs below a limit

Medium
Given a sorted array and a limit k, return how many pairs of positions have a sum strictly less than k.
Follow-up
A match no longer ends the walk, and adding one to the count per comparison caps you at n-1 pairs — which is wrong, since there can be n(n-1)/2 of them. One comparison has to be worth many pairs at once.
Show the hint
When a[L] + a[R] is under k, every element between L and R is no bigger than a[R], so it also pairs with a[L] under k — bank all R minus L of them in one go, then move L. Otherwise move R and count nothing.

Three numbers to a target

Medium
Given a sorted array and a target, return true if any three elements sum to the target.
Follow-up
You cannot two-pointer three values directly. Fix one element, then run the ordinary walk on the part after it — that is O(n²) overall, still far better than the O(n³) triple loop.
Show the hint
For each index i, walk two pointers over the elements after i looking for the value target minus a[i].

Container with most water

Hard
Given heights h[0] to h[n-1], return the largest value of min(h[L], h[R]) times the distance R minus L over all pairs.
Follow-up
The array is not sorted at all, so the discard rule has to come from geometry instead of order: moving the taller wall inward shrinks the width while the height stays capped by the shorter wall, so it can never help.
Show the hint
Always move the pointer standing at the shorter wall, and convince yourself that every pair you skip has both a smaller width and no greater height.