Lesson 05 of 2415 min read

Two Pointers

Your first real technique. Two indices walking a sequence, and a whole family of problems that look like they need nested loops but do not.

By the end: Replace a nested loop with two indices moving in one pass.

Two indices walking through a sequence. That is the whole idea, and it replaces a nested loop in a surprising number of problems.

There are three shapes. Learn to recognise which one a problem wants and most of the work is done.

Shape one: converging from the ends

The key insight is that on a sorted array, comparing the two ends tells you which pointer to move. If the sum is too small, the only way to increase it is to move the left pointer right. If it is too large, move the right pointer left. Each step eliminates a whole row of possibilities.

Two Sum on a sorted array: O(n) time, O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21function twoSumSorted(nums, target) {
  let lo = 0, hi = nums.length - 1;
  let steps = 0;
  while (lo < hi) {
    steps++;
    const sum = nums[lo] + nums[hi];
    if (sum === target) return { pair: [nums[lo], nums[hi]], steps };
    if (sum < target) lo++;        // need bigger: only lo can help
    else hi--;                     // need smaller: only hi can help
  }
  return { pair: null, steps };
}

console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 10));
console.log(twoSumSorted([2, 3, 4], 6));
console.log(twoSumSorted([1, 2], 99));

// Compare the step count with the nested-loop version at scale.
const sorted = Array.from({ length: 1000 }, (_, i) => i);
console.log('n=1000, two pointers:', twoSumSorted(sorted, 1997).steps, 'steps');
console.log('a nested loop would be up to', (1000 * 999 / 2).toLocaleString('en-US'), 'steps');

Output

Reversing in place, and checking a palindrome

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20function reverseInPlace(arr) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    [arr[lo], arr[hi]] = [arr[hi], arr[lo]];
    lo++; hi--;
  }
  return arr;
}
console.log(reverseInPlace([1, 2, 3, 4, 5]));
console.log(reverseInPlace(['a', 'b', 'c', 'd']));

function isPalindrome(s) {
  let lo = 0, hi = s.length - 1;
  while (lo < hi) {
    if (s[lo] !== s[hi]) return false;
    lo++; hi--;
  }
  return true;
}
console.log('racecar:', isPalindrome('racecar'), '| hello:', isPalindrome('hello'), '| empty:', isPalindrome(''));

Output

The container problem, worth studying closely

Given heights, pick two of them as the walls of a container; the water held is the shorter wall times the distance between them. Maximise it.

The greedy insight: move the pointer at the shorter wall. Why? The area is limited by the shorter wall. Moving the taller one inward can only reduce the width while the height stays capped by the same short wall, so it can never improve. Moving the shorter one is the only move that might help.

Maximum container area in one pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17function maxArea(heights) {
  let lo = 0, hi = heights.length - 1, best = 0;
  const log = [];
  while (lo < hi) {
    const h = Math.min(heights[lo], heights[hi]);
    const area = h * (hi - lo);
    if (area > best) { best = area; log.push(`new best ${area} using walls ${lo} and ${hi}`); }
    // Move the shorter wall: it is the binding constraint.
    if (heights[lo] < heights[hi]) lo++;
    else hi--;
  }
  return { best, log };
}

const r = maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]);
console.log('best area:', r.best);
r.log.forEach(l => console.log('  ' + l));

Output

Shape two: slow and fast, same direction

Here the pointers do different jobs. The fast pointer reads every element. The slow pointer marks where the next kept element should be written. This gives you in-place filtering in one pass with no extra space.

Remove duplicates from a sorted array, in place

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18function dedupeSorted(nums) {
  if (nums.length === 0) return 0;
  let write = 1;                          // nums[0] is always kept
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) { // different from the last kept value
      nums[write] = nums[read];
      write++;
    }
  }
  nums.length = write;
  return write;
}

const a = [1, 1, 2, 2, 2, 3, 4, 4];
console.log('kept', dedupeSorted(a), 'items →', a);

const b = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
console.log('kept', dedupeSorted(b), 'items →', b);

Output

Move zeroes to the end, keeping the order of the rest

1
2
3
4
5
6
7
8
9
10
11
12
13
14function moveZeroes(nums) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
  return nums;
}

console.log(moveZeroes([0, 1, 0, 3, 12]));
console.log(moveZeroes([0, 0, 1]));
console.log(moveZeroes([1, 2, 3]));

Output

Shape three: two sequences

Merging two sorted arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17function mergeSorted(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) out.push(a[i++]);   // advance whichever is smaller
    else out.push(b[j++]);
  }
  // One list is exhausted; append whatever is left of the other.
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}

console.log(mergeSorted([1, 3, 5], [2, 4, 6]));
console.log(mergeSorted([1, 2, 3], []));
console.log(mergeSorted([], [4, 5]));
console.log(mergeSorted([1, 1, 1], [1, 1]));

Output

This is the heart of merge sort, which is lesson 13. It is also the answer to "merge two sorted linked lists", a very common interview question, with the same logic and different plumbing.

Merging into a fixed array from the back

1
2
3
4
5
6
7
8
9
10
11
12
13// A twist that shows up often: a has extra space at the end, merge b into it
// in place. Filling from the BACK avoids overwriting values you still need.
function mergeInto(a, m, b, n) {
  let i = m - 1, j = n - 1, write = m + n - 1;
  while (j >= 0) {
    if (i >= 0 && a[i] > b[j]) a[write--] = a[i--];
    else a[write--] = b[j--];
  }
  return a;
}

console.log(mergeInto([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3));
console.log(mergeInto([0], 0, [1], 1));

Output

Three Sum: two pointers inside a loop

Now combine them. Fix one number with an outer loop, then use two pointers on the rest to find the pair that completes the triple. The sort makes the two-pointer step valid, and it also makes duplicate-skipping easy.

Three Sum: O(n squared), which is the expected answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26function threeSum(nums) {
  const out = [];
  const a = [...nums].sort((x, y) => x - y);

  for (let i = 0; i < a.length - 2; i++) {
    if (i > 0 && a[i] === a[i - 1]) continue;      // skip duplicate first values
    if (a[i] > 0) break;                            // sorted: no way to reach 0

    let lo = i + 1, hi = a.length - 1;
    while (lo < hi) {
      const sum = a[i] + a[lo] + a[hi];
      if (sum === 0) {
        out.push([a[i], a[lo], a[hi]]);
        while (lo < hi && a[lo] === a[lo + 1]) lo++;   // skip duplicate pairs
        while (lo < hi && a[hi] === a[hi - 1]) hi--;
        lo++; hi--;
      } else if (sum < 0) lo++;
      else hi--;
    }
  }
  return out;
}

console.log(threeSum([-1, 0, 1, 2, -1, -4]));
console.log(threeSum([0, 0, 0, 0]));
console.log(threeSum([1, 2, 3]));

Output

How to recognise it

Reach for two pointers when you see any of these:

The input is sorted, or sorting it does not break the problem.
You are looking for a pair or a triple that satisfies a condition.
The problem says in place or O(1) extra space.
You are comparing a sequence with itself from both ends, as in palindromes.
You need to merge two ordered sequences.

Your turn: three two-pointer problems

squaresOfSorted(nums) — given a sorted array that may contain negatives, return the squares in sorted order, in O(n). The largest square is at one end or the other, so fill the output from the back.
reverseVowels(s) — reverse only the vowels in a string, leaving everything else where it is. 'leetcode' becomes 'leotcede'.
trapRain(heights) — how much water is trapped between the bars. Harder: at each step the water above a bar is bounded by the tallest bar to its left and to its right; track a running max from each side and always move the smaller one.

Editable. Fill them in, then run.

function squaresOfSorted(nums) {
  // two pointers at the ends, write into the output from the back
}

function reverseVowels(s) {
  // two pointers, skip non-vowels, swap when both land on a vowel
}

function trapRain(heights) {
  // leftMax and rightMax, move the smaller pointer
}

console.log(squaresOfSorted([-4, -1, 0, 3, 10]));   // [0,1,9,16,100]
console.log(squaresOfSorted([-7, -3, 2, 3, 11]));   // [4,9,9,49,121]
console.log(reverseVowels('leetcode'));             // 'leotcede'
console.log(reverseVowels('hello'));                // 'holle'
console.log(trapRain([0,1,0,2,1,0,1,3,2,1,2,1]));   // 6
console.log(trapRain([4,2,0,3,2,5]));               // 9

Output

Recap

Two pointers replaces a nested loop, giving O(n) time and O(1) space.
Opposite ends needs sorted input: compare the ends to decide which pointer must move.
Slow-write plus fast-read is the template for every in-place filter and dedupe.
One pointer in each of two sequences is how you merge; fill from the back when merging in place.
Sort first, then two pointers inside a loop, is the standard O(n²) answer to Three Sum, and duplicate-skipping is what gets checked.

Shape one: converging from the ends

The container problem, worth studying closely

Shape two: slow and fast, same direction

Shape three: two sequences

Three Sum: two pointers inside a loop

How to recognise it

Your turn: three two-pointer problems

Recap

New writing, when it lands.