Skip to content
wannacode

Two pointers

In short: Two pointers that start at both ends of a sorted array and move towards each other find a pair with a given sum in O(n) instead of O(n²).

Problem

The gift card and every pair

A customer has a gift card and wants to spend it to the cent: two products that together cost exactly as much as the card. The site looks for them with two nested loops, checking every pair:

let checks = 0;


function allPairs(prices, card) {
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      checks++;
      if (prices[i] + prices[j] === card) {
        return [i, j];
      }
    }
  }
  return null;
}

The price list is 1000 products at €2, €4, …, €2000, and the card is for €2001. The sum of two even prices is never odd, so there is no pair. This is the worst case: the loops go all the way to the end.

const n = 1000;
const prices = Array.from({ length: n }, (_, i) => 2 * (i + 1));
const card = 2 * n + 1;
const pair = allPairs(prices, card);
console.log("Pair: " + (pair === null ? "none" : "found"));
console.log(`Checks: ${checks}`);
Output
Pair: none
Checks: 499500

Almost half a million checks for 1000 products. There are n(n − 1) / 2 pairs, so this is O(n²): for 100,000 products it becomes about 5 billion.

And the price list is sorted by price, yet the loops make no use of it.

The idea

One on the left, the other on the right

Put one finger on the cheapest price and another on the most expensive. The fingers are indexes: lo and hi. Add the two prices:

  • if the sum equals the card, you are done;
  • if it is too little, the cheap price drops out: even with the most expensive price still in play, it is not enough. lo moves one price to the right;
  • if it is too much, the expensive price drops out: it is too much even with the cheapest one. hi moves one price to the left.

Every step throws away one price for good, and no pair that is the answer gets lost. When lo and hi meet, the prices have run out. At most n − 1 steps: O(n).

This is called two pointers: two indexes that walk along the array, and every comparison says which one of them moves. Here they walk towards each other. You know the idea from binary search, where lo and hi hold the range. There every probe throws away half, here it throws away one price.

The condition is the same: the array has to be sorted. Only then is "to the right is more expensive" true.

See it

lo and hi in the price list

function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      lo++;
    } else {
      hi--;
    }
  }
  return null;
}
const prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
const pair = findPair(prices, 50);
if (pair === null) {
  console.log("No pair for €50");
} else {
  const [lo, hi] = pair;
  console.log(`€${prices[lo]} + €${prices[hi]}`);
}
Output
€19 + €31

function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      lo++;
    } else {
      hi--;
    }
  }
  return null;
}
Step by step, in words
  1. The price list is sorted: 10 prices. The gift card is €50. lo is on the cheapest price, hi on the most expensive.
  2. €3 + €36 = €39 < €50: too little. Even the most expensive price is not enough for €3, so €3 drops out: lo moves right.
  3. €5 + €36 = €41 < €50: too little. Even the most expensive price is not enough for €5, so €5 drops out: lo moves right.
  4. €8 + €36 = €44 < €50: too little. Even the most expensive price is not enough for €8, so €8 drops out: lo moves right.
  5. €12 + €36 = €48 < €50: too little. Even the most expensive price is not enough for €12, so €12 drops out: lo moves right.
  6. €15 + €36 = €51 > €50: too much. €36 is too much even with the cheapest price, so €36 drops out: hi moves left.
  7. €15 + €31 = €46 < €50: too little. Even the most expensive price is not enough for €15, so €15 drops out: lo moves right.
  8. €19 + €31 = €50: exactly the card. findPair returns the indexes 5 and 8.
  9. 7 sums instead of 45 pairs. Every step throws away one price for good, so there are at most n − 1 steps.
The function returns an array with the two indexes, and null when there is no pair. const [lo, hi] = pair splits them.
More precisely, if you are curious

Why no pair gets lost. Say the answer is the pair of indexes i and j, i < j. While lo ≤ i and hi ≥ j, the pointers cannot jump over the answer:

  • if lo < i, the sum of lo and hi is at most the sum of i and hi. If it is too little, lo rightly moves right without passing i;
  • if hi > j, in the same way hi rightly moves left without passing j.

When lo reaches i and hi reaches j, the sum is exactly the card. If there are several pairs, the pointers find the outermost one: the one with the cheapest price.

Try it

Predict which pair

The card is €43. The price list has two pairs with that sum: €12 + €31 and €19 + €24. What does the program print?

function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      lo++;
    } else {
      hi--;
    }
  }
  return null;
}


const prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
const pair = findPair(prices, 43);
if (pair === null) {
  console.log("No pair for €43");
} else {
  const [lo, hi] = pair;
  console.log(`€${prices[lo]} + €${prices[hi]}`);
}
Answer

Try it

Fill in

The sum is smaller than the card. Which pointer moves, and which way?

function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      ;
    } else {
      hi--;
    }
  }
  return null;
}

Try it

Find the bug

The card is €50, and €19 + €31 is in the price list. The function says there is no pair:

const prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
const pair = findPair(prices, 50);
if (pair === null) {
  console.log("No pair for €50");
} else {
  const [lo, hi] = pair;
  console.log(`€${prices[lo]} + €${prices[hi]}`);
}
Output
No pair for €50

Pick the line with the bug.

See it

How many steps

The same price list of 1000 products and the card for €2001, and the function counts the steps of its loop:

let steps = 0;


function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    steps++;
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      lo++;
    } else {
      hi--;
    }
  }
  return null;
}
const n = 1000;
const prices = Array.from({ length: n }, (_, i) => 2 * (i + 1));
const card = 2 * n + 1;
const pair = findPair(prices, card);
console.log("Pair: " + (pair === null ? "none" : "found"));
console.log(`Steps: ${steps}`);
Output
Pair: none
Steps: 999

999 steps instead of 499,500 checks. The two functions give the same answer, and for 100,000 products the difference is 99,999 steps against about 5 billion.

Run them in the browser. The third curve is for an unsorted price list: first merge sort, then the two pointers.

  • Every pair O(n²)
  • Two pointers (sorted list) O(n)
  • Sort, then two pointers O(n log n)
Algorithmn = 10n = 1,000n = 10,000n = 100,000
Every pair45499,50049,995,000≈ 4,999,500,000
Two pointers (sorted list)99999,99999,999
Sort, then two pointers319,692130,4241,636,539
The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.
function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      lo++;
    } else {
      hi--;
    }
  }
  return null;
}

We do not run every pair above 10,000: those values are ≈. Sorting costs more than the pointers themselves, but its curve is O(n log n) and still far below O(n²).

The idea

Is the list sorted

Two pointers need a sorted array. When it is not:

  • Sort it first. Sorting is O(n log n), the pointers O(n), in total O(n log n). For 100,000 prices that is about 1.6 million operations against about 5 billion. Sorting wins almost every time.
  • If you search many times in the same list (every customer with a different card), you sort once, and every search after that is O(n).
  • The indexes change. After sorting, prices[5] is no longer the fifth product of the catalogue. If you need the products, sort pairs (price, product) or objects by price.
const prices = [27, 3, 36, 15, 8, 31, 19, 5, 24, 12];
prices.sort((a, b) => a - b);
console.log("[" + prices.join(", ") + "]");
const pair = findPair(prices, 50);
if (pair === null) {
  console.log("No pair for €50");
} else {
  const [lo, hi] = pair;
  console.log(`€${prices[lo]} + €${prices[hi]}`);
}
Output
[3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
€19 + €31

sort() in JavaScript without a compare function sorts the numbers as text: "12" comes before "3", because "1" comes before "3". For numbers you always pass (a, b) => a - b. Without it the two pointers start on the wrong order and miss pairs:

const prices = [27, 3, 36, 15, 8, 31, 19, 5, 24, 12];
prices.sort();
console.log("[" + prices.join(", ") + "]");
Output
[12, 15, 19, 24, 27, 3, 31, 36, 5, 8]

There is also a way without sorting: you go over the prices once and keep the ones you have seen in a set. For each price you ask whether card − price has already been seen. That is O(n) on average, with a hash table and n extra memory. Two pointers use no extra memory, but they need a sorted array.

See it

The same idea: merging and duplicates

The two pointers do not always walk towards each other. Sometimes they walk in the same direction.

Merging two sorted lists. The orders from the website and from the phone are numbered by one counter but kept apart, each list sorted. The daily report wants one sorted list. i walks along the first, j along the second, and each time the smaller number goes into the result. This is the merge from merge sort:

function merge(a, b) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) {
      result.push(a[i++]);
    } else {
      result.push(b[j++]);
    }
  }
  while (i < a.length) {
    result.push(a[i++]);
  }
  while (j < b.length) {
    result.push(b[j++]);
  }
  return result;
}
const web = [1003, 1007, 1012, 1020];
const phone = [1001, 1009, 1010, 1031, 1044];
console.log("[" + merge(web, phone).join(", ") + "]");
Output
[1001, 1003, 1007, 1009, 1010, 1012, 1020, 1031, 1044]

Duplicates in place. The prices from an import are sorted, but with duplicates, and the filter has to show every price once. read reads every price, and write is the place for the next new one. Everything before write is finished and free of duplicates:

function unique(prices) {
  if (prices.length === 0) {
    return 0;
  }
  let write = 1;
  for (let read = 1; read < prices.length; read++) {
    if (prices[read] !== prices[write - 1]) {
      prices[write] = prices[read];
      write++;
    }
  }
  return write;
}
const prices = [5, 5, 8, 12, 12, 12, 19, 24, 24];
const k = unique(prices);
prices.length = k;
console.log(`Different prices: ${k}`);
console.log("[" + prices.join(", ") + "]");
Output
Different prices: 5
[5, 8, 12, 19, 24]
An array in JavaScript can be shortened in place: prices.length = k removes everything after the first k.

Both are O(n): each pointer goes over the list once.

See it

A mirror promo code

The "Mirror code" campaign accepts only promo codes that read the same from both ends. The pointers start at both ends and compare character by character until they meet:

function isMirror(code) {
  let lo = 0;
  let hi = code.length - 1;
  while (lo < hi) {
    if (code[lo] !== code[hi]) {
      return false;
    }
    lo++;
    hi--;
  }
  return true;
}
console.log(isMirror("AB7CC7BA"));
console.log(isMirror("AB7CD7BA"));
Output
true
false
More precisely, if you are curious

The same check can be written on one line, by comparing the code with a reversed copy:

const code = "AB7CC7BA";
console.log(code === [...code].reverse().join(""));
Output
true
[...code].reverse().join("") makes an array of the characters, reverses it and joins it into a new string.

The answer is the same and it is still O(n). The difference: the copy is n more characters of memory and is always made in full, while the pointers stop at the first difference. For an 8-character promo code it does not matter. For checking millions of lines in a log it does.

The same pointers reverse an array in place: swap lo and hi, move them inwards.

Exercise

Closest to the card

Solve the task in your editor.

Closest to the card. There is not always an exact pair. Then the shop offers the two products that together come closest to the card without going over it. The price list is €3, €5, €8, €12, €15, €19, €24, €27, €31 and €36, and the card is €45. With two pointers: if the sum is within the card, remember it if it is better than the best so far, and move lo. Otherwise move hi.

Output
Closest to €45: €8 + €36 = €44

More tasks

  • A mirror code with dashes. The promo codes are printed with dashes: AB7-CC-7BA. Skip the dashes: each pointer jumps over them before comparing.
  • Two per trip. The parcels are sorted by weight, and one courier trip carries at most two parcels of up to 30 kg in total. How many trips are needed at the least? Put the lightest with the heaviest if they fit, otherwise the heaviest goes alone.
  • Common products. Two sorted lists of product numbers: from the warehouse and from the order. Find which numbers are in both, with two pointers in the same direction.

Test

Check yourself

1. The price list is sorted. lo is on €8, hi on €36, the card is €50. The sum is €44. What do you do?
2. The price list has 100,000 products, and there is no pair for the card. How many sums do the two pointers compute?
3. The price list is not sorted. Which of the three is fastest?
4. You remove the duplicates from the sorted list in place, with read and write. Which is true?
5. Why is checking a mirror promo code with two pointers better than comparing it with a reversed copy?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·