Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Two Pointers

The two pointers pattern uses two indexes moving through an array or string to replace a nested loop. How it works, when it applies, and templates.

The two pointers pattern keeps two indexes into the same array or string and moves them according to a rule. Because each pointer only ever moves in one direction, the whole input is covered in a single pass.

The idea

A brute-force search for a pair of items compares every item with every other item: O(n²). Two pointers avoids that by using some structure in the data, most often sorted order, to decide which pointer to move. Each move rules out many pairs at once without checking them.

When to use it

  • The input is a sorted array and you need a pair with some property, such as a target sum.
  • You are comparing a sequence with itself from both ends, as in a palindrome check.
  • You need to rearrange or filter an array in place, without a second array.
  • The problem asks for O(1) extra space.

Form 1: pointers at opposite ends

Start one pointer at the first item and one at the last, and move them towards each other.

function pairWithSum(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
 
  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum === target) return [left, right];
    if (sum < target) {
      left++;   // need a larger sum
    } else {
      right--;  // need a smaller sum
    }
  }
  return null;
}

Walkthrough

pairWithSum([1, 3, 4, 6, 8, 11], 10):

left (value) right (value) Sum Action
0 (1) 5 (11) 12 Too large: move right
0 (1) 4 (8) 9 Too small: move left
1 (3) 4 (8) 11 Too large: move right
1 (3) 3 (6) 9 Too small: move left
2 (4) 3 (6) 10 Found: return [2, 3]

Five sums were checked. Trying every pair of six values would mean fifteen.

Why this is correct

The array is sorted, so sorted[left] is the smallest remaining value and sorted[right] is the largest.

  • If the sum is too small, pairing sorted[left] with any other remaining value would give a sum that is no larger, because sorted[right] is already the largest partner available. So sorted[left] cannot be part of the answer, and it is safe to move left forward.
  • If the sum is too large, the same argument rules out sorted[right].

Each step discards one value for good, so the loop ends after at most n steps.

Form 2: pointers moving in the same direction

Both pointers start at the front. A fast pointer reads every item; a slow pointer marks where the next kept item should go. This removes items in place.

// Remove duplicates from a sorted array in place; returns the new length.
function removeDuplicates(sorted) {
  if (sorted.length === 0) return 0;
 
  let slow = 0;
  for (let fast = 1; fast < sorted.length; fast++) {
    if (sorted[fast] !== sorted[slow]) {
      slow++;
      sorted[slow] = sorted[fast];
    }
  }
  return slow + 1;
}

Walkthrough

removeDuplicates([1, 1, 2, 3, 3, 3, 4]):

fast (value) Same as the value at slow? Action Array so far slow
1 (1) Yes Skip 1, 1, 2, 3, 3, 3, 4 0
2 (2) No Keep it at index 1 1, 2, 2, 3, 3, 3, 4 1
3 (3) No Keep it at index 2 1, 2, 3, 3, 3, 3, 4 2
4 (3) Yes Skip 1, 2, 3, 3, 3, 3, 4 2
5 (3) Yes Skip 1, 2, 3, 3, 3, 3, 4 2
6 (4) No Keep it at index 3 1, 2, 3, 4, 3, 3, 4 3

The function returns 4. The first four positions hold 1, 2, 3, 4; whatever is after them is left over and ignored.

Form 3: one pointer in each of two arrays

The two pointers do not have to be in the same array. Merging two sorted arrays keeps one index in each and always takes the smaller of the two front values.

function mergeSorted(first, second) {
  const merged = [];
  let i = 0;
  let j = 0;
 
  while (i < first.length && j < second.length) {
    if (first[i] <= second[j]) {
      merged.push(first[i++]);
    } else {
      merged.push(second[j++]);
    }
  }
  // One array has run out; the rest of the other is already in order.
  while (i < first.length) merged.push(first[i++]);
  while (j < second.length) merged.push(second[j++]);
  return merged;
}

Each step moves one pointer forward and neither ever goes back, so the cost is the total length of the two arrays.

Other forms you will meet

Form How the pointers move Example
Fix one, then opposite ends An outer loop fixes a value; two pointers search the rest 3Sum
Move the weaker side Both start at the ends; the one on the smaller value moves Container With Most Water
Fast and slow One moves two steps for the other's one Linked list pointer techniques
A range that grows and shrinks Both move right, a varying distance apart Sliding window

The question to ask

Two pointers works when you can say, at each step, which pointer to move and why nothing is lost by moving it. In the sorted pair search the reason is that the value left behind cannot be part of any answer. If you cannot state that reason for a problem, the pattern probably does not apply to it.

Complexity

  • Time: O(n). Each pointer crosses the input at most once.
  • Space: O(1). Only the two indexes are stored.

If the input is not sorted and you sort it first, the total becomes O(n log n) for the sort.

Common mistakes

  • Using it on unsorted data. The opposite-ends form depends on sorted order. If you cannot sort, for example because you need the original indexes, use hashing instead.
  • Using left <= right when a pair is needed. When the pointers meet they refer to the same item, which is not a pair. Use left < right.
  • Moving both pointers when only one should move. After a mismatch, move only the pointer the rule tells you to.
  • Forgetting what is left in the array. The same-direction form returns a new length. Items beyond it are leftovers, not part of the result.
  • Skipping equal values without care. When the input has repeats and every answer is wanted, decide deliberately how to step past them, as 3Sum does.

Practise

  1. Valid Palindrome (easy): opposite ends.
  2. Two Sum on a Sorted Array (medium): the pair search above.
  3. 3Sum (medium): fix one value, then search.
  4. Container With Most Water (medium): move the weaker side.
  5. Trapping Rain Water (hard): the same rule, applied to every bar.

Practice problems

ProblemDifficultyTimeSpaceRead
Valid PalindromeeasyO(n)O(1)Quick read: 3 min
3SummediumO(n²)O(n)Medium read: 6 min
Container With Most WatermediumO(n)O(1)Short read: 5 min
Two Sum on a Sorted ArraymediumO(n)O(1)Quick read: 3 min
Trapping Rain WaterhardO(n)O(1)Medium read: 8 min