Two Pointers

Two indices instead of two loops

Many array problems look at pairs of items. The obvious solution is a loop inside a loop, which costs O(n²) steps. The two-pointer technique uses two indices (called pointers) instead of two loops. Each pointer moves through the array only once, so the total is O(n). It comes in two forms:

• From both ends. The pointers start at the two ends and move towards each other. You usually use this on a sorted array.
• In the same direction. One pointer stays ahead of the other. This is the read/write pattern from Lesson 19.

The main skill is knowing which pointer to move. You must also be able to explain why that move cannot skip the answer.

Pair sum in a sorted array

Find two values in a sorted array (smallest first) that add up to a target. Put l (left) at the start and r (right) at the end. If the sum is too small, the only way to make it bigger is to move l to the right. If the sum is too big, move r to the left.

Traced: find two values adding to 10

▶const nums = [1, 3, 4, 6, 8, 11];2const target = 10;3let l = 0, r = nums.length - 1;4while (l < r) {5  const sum = nums[l] + nums[r];6  if (sum === target) break;7  if (sum < target) l++;8  else r--;9}10console.log(l, r);

Why it never misses the answer

Interviewers often ask this question. Say nums[l] + nums[r] is too small. Because the array is sorted, every other partner for nums[l] is at most nums[r]. So every pair that uses nums[l] is also too small. This means nums[l] cannot be part of the answer, and moving l loses nothing. The “too big” case is the same idea from the other side. Each move removes one value that we can prove is not needed.

Same-direction pointers

In the second form, both pointers move forward, but at different speeds. Lesson 19 used it to remove duplicates and to move zeros. Here is another classic problem. A subsequence of a string is made by taking some of its letters in the same order. The letters do not have to be next to each other. For example, “ace” is a subsequence of “abcde”. The task is to check whether one string is a subsequence of another.

// Is s a subsequence of t? (Letters of s appear in t in order, not necessarily together.)function isSubsequence(s, t) {  let i = 0;                                  // position in s  for (let j = 0; j < t.length && i < s.length; j++) {    if (s[i] === t[j]) i++;                   // matched one more letter of s  }  return i === s.length;}console.log(isSubsequence("ace", "abcde")); // trueconsole.log(isSubsequence("aec", "abcde")); // false

j moves at every step. i moves only when it finds a match. This takes O(n + m) steps (n and m are the two string lengths). You do not have to try every way of picking letters. The sliding windows in Lessons 22 and 23 also use pointers that move in the same direction.

3Sum: fix one, two-pointer the rest

Find all unique triples (groups of three values) that add up to 0. Three nested loops cost O(n³). Do this instead. First sort the array. Then fix the first value nums[i]. Then use the pair-sum two pointers on the rest of the array, to find two values that add up to -nums[i].

function threeSum(nums) {  nums.sort((a, b) => a - b);  const out = [];  for (let i = 0; i < nums.length - 2; i++) {    if (i > 0 && nums[i] === nums[i - 1]) continue;      // same first value: skip    let l = i + 1, r = nums.length - 1;    while (l < r) {      const sum = nums[i] + nums[l] + nums[r];      if (sum < 0) l++;      else if (sum > 0) r--;      else {        out.push([nums[i], nums[l], nums[r]]);        l++;        r--;        while (l < r && nums[l] === nums[l - 1]) l++;    // skip repeated second values      }    }  }  return out;}console.log(threeSum([-1, 0, 1, 2, -1, -4]));// [ [ -1, -1, 2 ], [ -1, 0, 1 ] ]

Sorting costs O(n log n). Then you run one O(n) two-pointer pass for each of the n first values. The total is O(n²). To avoid repeated triples, skip a value that is equal to the one you just used. Do this for i and for l. The sort makes this easy, because it puts equal values next to each other.

Container with most water

A vertical line of a different height stands at each index. Choose two lines. The water they can hold is min(height[l], height[r]) × (r − l). (The water level is set by the shorter line, and the width is the distance between the lines.) Start with the widest pair. Then move the shorter line inwards. Keeping it cannot help. Any narrower container that still uses it is limited by the same short height, and it is also narrower.

function maxArea(height) {  let l = 0, r = height.length - 1, best = 0;  while (l < r) {    const area = Math.min(height[l], height[r]) * (r - l);    best = Math.max(best, area);    if (height[l] < height[r]) l++;     // the shorter line limits the area: move it    else r--;  }  return best;}console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49

Three-way partition (Dutch national flag)

Lesson 18 partitioned (split) an array around a pivot into two groups. With three pointers you can split an array into three groups in one pass. A common example is sorting an array that has only 0s, 1s and 2s. It is called the Dutch national flag problem because the flag has three colour bands. The meaning of the pointers:

• everything before low is 0;
• everything after high is 2;
• everything between low and mid is 1;
• mid is the item we are checking now.

function sortColors(nums) {  let low = 0, mid = 0, high = nums.length - 1;  while (mid <= high) {    if (nums[mid] === 0) {      [nums[low], nums[mid]] = [nums[mid], nums[low]];      low++;      mid++;    } else if (nums[mid] === 1) {      mid++;    } else {      [nums[mid], nums[high]] = [nums[high], nums[mid]];      high--;                                // do not move mid: the new value is unchecked    }  }  return nums;}console.log(sortColors([2, 0, 2, 1, 1, 0])); // [ 0, 0, 1, 1, 2, 2 ]

The templates side by side

Practice questions

For every two-pointer answer, be ready to say in one sentence why the pointer you move cannot be part of a better answer.

function twoSum(numbers, target) {  const seen = new Map();  for (let i = 0; i < numbers.length; i++) {    const j = seen.get(target - numbers[i]);    if (j !== undefined) return [j + 1, i + 1];    seen.set(numbers[i], i);  }}console.log(twoSum([2, 7, 11, 15], 9)); // [ 1, 2 ]

function twoSum(numbers, target) {  let l = 0, r = numbers.length - 1;  while (l < r) {    const sum = numbers[l] + numbers[r];    if (sum === target) return [l + 1, r + 1];    if (sum < target) l++;    else r--;  }}console.log(twoSum([2, 7, 11, 15], 9)); // [ 1, 2 ]console.log(twoSum([-1, 0], -1));       // [ 1, 2 ]

function reverseVowels(s) {  const vowels = new Set("aeiouAEIOU");  const a = [...s];  let l = 0, r = a.length - 1;  while (l < r) {    if (!vowels.has(a[l])) l++;    else if (!vowels.has(a[r])) r--;    else {      [a[l], a[r]] = [a[r], a[l]];      l++;      r--;    }  }  return a.join("");}console.log(reverseVowels("IceCreAm")); // AceCreImconsole.log(reverseVowels("leetcode")); // leotcede

function isSubsequence(s, t) {  let i = 0;  for (let j = 0; j < t.length && i < s.length; j++) {    if (s[i] === t[j]) i++;  }  return i === s.length;}console.log(isSubsequence("abc", "ahbgdc")); // trueconsole.log(isSubsequence("axc", "ahbgdc")); // falseconsole.log(isSubsequence("", "abc"));       // true

function threeSum(nums) {  const found = new Map();  for (let i = 0; i < nums.length; i++)    for (let j = i + 1; j < nums.length; j++)      for (let k = j + 1; k < nums.length; k++)        if (nums[i] + nums[j] + nums[k] === 0) {          const t = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);          found.set(t.join(","), t);        }  return [...found.values()];}console.log(threeSum([0, 0, 0, 0])); // [ [ 0, 0, 0 ] ]

function threeSum(nums) {  nums.sort((a, b) => a - b);  const out = [];  for (let i = 0; i < nums.length - 2; i++) {    if (nums[i] > 0) break;                              // three positives cannot sum to 0    if (i > 0 && nums[i] === nums[i - 1]) continue;    let l = i + 1, r = nums.length - 1;    while (l < r) {      const sum = nums[i] + nums[l] + nums[r];      if (sum < 0) l++;      else if (sum > 0) r--;      else {        out.push([nums[i], nums[l], nums[r]]);        l++; r--;        while (l < r && nums[l] === nums[l - 1]) l++;      }    }  }  return out;}console.log(threeSum([-1, 0, 1, 2, -1, -4])); // [ [ -1, -1, 2 ], [ -1, 0, 1 ] ]console.log(threeSum([0, 0, 0, 0]));          // [ [ 0, 0, 0 ] ]

function threeSumClosest(nums, target) {  nums.sort((a, b) => a - b);  let best = nums[0] + nums[1] + nums[2];  for (let i = 0; i < nums.length - 2; i++) {    let l = i + 1, r = nums.length - 1;    while (l < r) {      const sum = nums[i] + nums[l] + nums[r];      if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;      if (sum < target) l++;      else if (sum > target) r--;      else return sum;                      // exact match: cannot do better    }  }  return best;}console.log(threeSumClosest([-1, 2, 1, -4], 1)); // 2console.log(threeSumClosest([0, 0, 0], 1));      // 0

function maxArea(h) {  let best = 0;  for (let i = 0; i < h.length; i++)    for (let j = i + 1; j < h.length; j++)      best = Math.max(best, Math.min(h[i], h[j]) * (j - i));  return best;}console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49

function maxArea(h) {  let l = 0, r = h.length - 1, best = 0;  while (l < r) {    best = Math.max(best, Math.min(h[l], h[r]) * (r - l));    if (h[l] < h[r]) l++;    else r--;  }  return best;}console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49console.log(maxArea([1, 1]));                      // 1

function numRescueBoats(people, limit) {  people.sort((a, b) => a - b);  let l = 0, r = people.length - 1, boats = 0;  while (l <= r) {    if (people[l] + people[r] <= limit) l++;   // lightest joins the heaviest    r--;                                        // heaviest always leaves    boats++;  }  return boats;}console.log(numRescueBoats([3, 2, 2, 1], 3)); // 3console.log(numRescueBoats([3, 5, 3, 4], 5)); // 4

Make it stick

What's next

Lesson 22 turns same-direction pointers into a sliding window. A sliding window is a block of k items that moves one step at a time. Each time it moves, you update its sum or count in O(1) (one quick step) and you do not need to count it again from the start.