cf.completefrontend
TWO POINTERS · CORE

Two pointers from opposite ends

Put one index at the start and one at the end of a list, and move them toward each other to check pairs without a nested loop.

Time O(n)Space O(1)16 practice problemsStep-through picture

The idea

Many questions ask about pairs of items: two prices that add up to a gift card, the first and last letters of a word, the two walls that hold the most water. The slow way checks every pair with two loops, one inside the other. A list of 1,000 items has about 500,000 pairs.

The two-pointer way keeps two indexes. left starts at the first item and right starts at the last item. At each step you look at the pair nums[left] and nums[right], and a simple rule tells you which index to move inward. The indexes meet in the middle after at most n steps.

The rule only works when the list has some order you can trust. Most often the list is sorted: then moving left right makes the sum bigger, and moving right left makes it smaller. For a word, the order is simply the position of each letter.

An everyday example

Two people packing a seesaw

Kids stand in a line from lightest to heaviest, and you want two kids whose weights add up to exactly 60 kg. You call the lightest kid and the heaviest kid. If together they weigh too much, the heaviest kid is too heavy for anyone in the line, so they sit down. If together they weigh too little, the lightest kid is too light for anyone, so they sit down. Each call removes one kid, so you are done after one walk down the line.

How the example maps to the code
In the exampleIn the code
The lightest kid still standingnums[left]
The heaviest kid still standingnums[right]
Their weight togetherconst sum = nums[left] + nums[right]
Too light: the lightest kid sits downleft++
Too heavy: the heaviest kid sits downright--

From the slow way to two pointers from opposite ends

  1. Start with the obvious way: try every pair. Two loops, i and j > i, check nums[i] + nums[j] against target. For 7 numbers that is 21 pairs, and for 100,000 numbers it is about 5 billion. Worse, it ignores the one useful fact we were given: the list is sorted.
  2. Use the order by looking at the two extremes first: the smallest item plus the largest item. Suppose that sum is too small. The largest item is the biggest partner the smallest item could ever get, and even that isn't enough. So the smallest item can't be in any answer pair, and you can drop it for good.
  3. The same reasoning works the other way. If the smallest plus the largest is too big, the smallest item is the kindest partner the largest item could get, and it still overshoots. So the largest item can't be in any answer pair. Either way, one check removes one item from the list of possibilities.
  4. Keep the items still in play as a range with two indexes: left for its smallest item and right for its largest. Each check either finds the pair or moves one index inward, so after at most n - 1 checks the range is empty. That loop is two pointers from opposite ends.

How it works

  1. Sort the list if it isn't sorted yet and the answer allows it.
  2. Put left at index 0 and right at the last index, nums.length - 1.
  3. While left < right, look at the pair: sum = nums[left] + nums[right].
  4. If sum equals the target, you found the pair: return [left, right].
  5. If sum is too small, the item at left can't be part of any answer, so move left one step right.
  6. If sum is too big, the item at right can't be part of any answer, so move right one step left.
  7. When left meets right, every possible pair has been ruled out: return [-1, -1].

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function pairWithSum(nums, target) {
  2. let left = 0;
  3. let right = nums.length - 1;
  4. while (left < right) {
  5. const sum = nums[left] + nums[right];
  6. if (sum === target) return [left, right];
  7. if (sum < target) {
  8. left++;
  9. } else {
  10. right--;
  11. }
  12. }
  13. return [-1, -1];
  14. }

How fast it is

TimeO(n)
Extra memoryO(1)

Each step moves one pointer one place closer to the other, so the loop runs at most n - 1 times. It only keeps two indexes and a sum. Add O(n log n) if the list must be sorted first.

  • Best caseO(1)

    The first and last items already add up to target, like [2, 6, 9, 15] with target = 17: the first check returns.

  • Average caseO(n)

    The pair sits somewhere in the middle, so the pointers walk part of the way before meeting it. Each step costs one addition and one comparison.

  • Worst caseO(n)

    No pair adds up to target, so the pointers walk until they meet: exactly n - 1 checks. If the list must be sorted first, the total is O(n log n).

Common mistakes

  • Using it on an unsorted list for a sum question. The rule "too small, so move left" is only true when the items are sorted. Sort first, or use a hash map instead.
  • Writing while (left <= right). When the pointers are equal, the loop pairs an item with itself, which can return a wrong pair like [2, 2].
  • Sorting the list and then returning indexes when the question wants the original positions. Sort pairs of [value, originalIndex], or return the values instead.
  • Moving both pointers after a mismatch in a sum question. Only one item is ruled out per step; moving both can skip the answer.

When to use it

Look for these clues in a problem:

  • The input is sorted, or sorting it doesn't change the answer, and the question is about a pair of items.
  • The question compares the start of a list or string with its end, such as "reads the same both ways".
  • You must answer in one pass with O(1) extra memory, so a hash map is not allowed.
  • The question asks for the best pair (closest sum, widest gap, most area) and a pair's value depends on the two ends.

Check yourself

Answer each one in your head first, then open it.

Why is left++ safe when the sum is too small?

nums[right] is the largest item still in play, and even it can't make nums[left] reach target. Every other partner is smaller, so nums[left] is in no answer pair.

What goes wrong with while (left <= right)?

When left === right, the loop pairs an item with itself. For [1, 4, 9] and target = 8, it would return [1, 1], using 4 twice.

At most how many checks does it make on 1,000 sorted numbers?

999. Each check either returns or moves one pointer one step closer to the other, and they start 999 apart.

Why can't you move both pointers after a mismatch in a sum question?

A mismatch proves only one item is useless. The other might still be part of an answer with a different partner, so moving it could skip the pair.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 16 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one promise: if some pair of indexes p < q has nums[p] + nums[q] === target, then such a pair lies inside the range, with left <= p and q <= right. At the start the range is the whole list, so the promise holds.

Each move keeps it. When sum < target, every q in the range has nums[q] <= nums[right], because the list is sorted, so nums[left] + nums[q] <= sum < target. No answer pair uses index left, and left++ drops only that index. When sum > target, the mirror argument shows no answer pair uses right, so right-- is safe.

The loop ends because right - left shrinks by one on every step that doesn't return. If it returns, the pair is a real match. If it ends with left === right, the range holds no pairs, so the promise says no answer pair exists, and [-1, -1] is correct.

Going deeper

3 more ideas

Why moving one pointer never skips the answer

Say nums[left] + nums[right] is smaller than the target. nums[right] is the biggest item still in play, so nums[left] plus any other item is even smaller. No pair that uses nums[left] can reach the target, so throwing left away is safe. The same reasoning, flipped, makes right-- safe when the sum is too big. Each step only throws away an item that can't be in any answer.

Why it takes O(n) time

Every step moves left right or right left by one. They start n - 1 apart and the loop stops when they meet, so there are at most n - 1 steps. If you must sort first, sorting costs O(n log n), and that becomes the total.

The same walk without a sorted list

Checking if a word reads the same both ways uses the same two indexes but a different rule. Compare word[left] with word[right]. If they differ, the answer is no. If they match, move both pointers inward. Here both pointers move every step, because a matched pair is finished.

Work it by hand

Every step in a table, with why

Find two numbers that add up to 32 in a sorted list of 7. The pointers move from both sides before they find the pair.

nums = [3, 5, 9, 14, 18, 21, 26], target = 32

Stepleftrightnums[left]nums[right]sumWhat happensWhy
1063262929 < 32, so left++The smallest and largest items. Even 26 can't lift 3 to 32, so 3 is out.
2165263131 < 32, so left++Still too small: 5 is out for the same reason.
3269263535 > 32, so right--Now too big. Even the smallest item left, 9, makes 26 overshoot, so 26 is out.
4259213030 < 32, so left++The pointers can switch direction at any step: this time left moves again.
53514213535 > 32, so right--21 is out: paired with the smallest item left, 14, it is already too big.
634141832Match: return [3, 4]14 + 18 = 32, so the function returns both indexes.

It returns [3, 4] after 6 checks. Checking every pair would have needed up to 21. The trace ends at the match; without one, it would end when left reached right.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Two pointers from opposite endsO(n)O(1)The list is already sorted and you need a pair, a closest pair, or a count of pairs, with no extra memory.
Hash map of complementsO(n)O(n)The list is unsorted and you need the original indexes. Store each value's index and look up target - nums[i] as you go.
Sort, then two pointersO(n log n)O(n)The list is unsorted, but you only need the values or a count, and you want the two-pointer walk's simplicity.
Check every pairO(n^2)O(1)The list is tiny, or you need a quick, obviously correct version to test the fast one against.

Extra memory: O(1): two indexes and one sum. Sorting a copy first, to keep the caller's array unchanged, would add O(n).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Two pointers from opposite ends and the other approaches, on a scale where each line up is 10 times more steps.
  • Two pointers from opposite ends, Hash map of complements O(n)
  • Sort, then two pointers O(n log n)
  • Check every pair O(n^2)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Two pointers from opposite ends101,0001 million
Hash map of complements101,0001 million
Sort, then two pointers339,96620 million
Check every pair1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty list or one item: nums = [] or nums = [4]
right starts at -1 or 0, so left < right is false and the function returns [-1, -1] without a check.
The same item can't be used twice: nums = [1, 4, 9], target = 8
4 + 4 would be 8, but left < right keeps the indexes different. The walk checks 10, then 5, then stops: [-1, -1].
Equal values at different indexes: nums = [4, 4], target = 8
They are two different items, so the first check returns [0, 1].
Several pairs work: nums = [1, 2, 3, 4, 5, 6], target = 7
It returns the first one it meets, the outermost pair [0, 5]. To list every pair, save the match and move both pointers instead of returning.
An unsorted list: nums = [9, 1, 5], target = 6
The rule breaks: 9 + 5 is too big, so it drops 5 and then misses 1 + 5, returning [-1, -1]. Sort first, or use a hash map of complements.

Variations and follow-ups

Twists interviewers add

Closest sum

When no exact match is required, keep the sum with the smallest Math.abs(sum - target) and move the pointers by the same rule. The same proof shows the closest pair is never skipped.

Counting pairs below a target

If nums[left] + nums[right] < target, then nums[left] pairs with every index from left + 1 to right, so add right - left to the count at once and move left. This counts all such pairs in O(n).

Widest container

For walls of different heights, the water held is Math.min(height[left], height[right]) * (right - left). Always move the shorter wall: keeping it can never give a bigger area, since the width only shrinks.

Comparing ends of a string

Checking whether a word reads the same both ways uses the same two indexes but moves both after each match. Reversing an array in place swaps items[left] and items[right] and moves both inward too.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "sorted" plus "pair", or from a question that compares the start of a list with its end. If the list isn't sorted but the answer doesn't depend on positions, sorting first is often allowed.
  • Explain the move rule with the reason, not just the rule: "if the sum is too small, even the largest item can't help nums[left], so nums[left] can't be in any answer." That one sentence is the whole proof.
  • Test by hand: a list with no answer (the pointers should meet), a list of two items, and a target that needs the same item twice, which must not be allowed.
  • Expect the follow-up "what if the list isn't sorted and you need the original indexes?". The answer is a hash map of value to index, O(n) time and O(n) space, or sorting pairs of [value, index].

Where frontend code uses it

The same idea in real UI code
  • Checking if a string reads the same both ways, such as a puzzle input or a mirrored icon name, is a two-pointer walk from both ends of the string.
  • Reversing an array in place, which Array.prototype.reverse does without making a copy, swaps items[left] and items[right] while the indexes move inward.
  • A date range picker that needs two sorted prices, durations, or sizes that add up to a limit can find them with one inward walk instead of a nested loop.

Related algorithms