pattern heroPT–23LeetCode Extension

Two pointers

Solve it with two pointers: two positions in the data that move by a rule. Where they go depends on the problem. What matters is that the data is walked once instead of trying every pair.

Variant
P02 Two pointersTowards each other · 1×

Example problem: find the indices of two numbers in the sorted array [2, 3, 5, 8, 9, 12, 16, 19] that add up to 17.

0213253849512616719left
still possiblethe pair being checkedruled outthe pair found

left starts at the smallest, 2

left = 0right = –sum = –
01/26
restart · back · play · step
Speed
1function pairWithSum(nums, target):
2 left = 0
3 right = len(nums) - 1
4 while left < right:
5 sum = nums[left] + nums[right]
6 if sum < target:
7 left = left + 1
8 else if sum > target:
9 right = right - 1
10 else:
11 return [left, right]

← → step · space play/pause

How to recognise

a sorted array and a pair or triple with a given sum, a palindrome check, or anything you compare from both ends.

How to solve problems like this

  1. Sort the input first if you do not need the original positions.
  2. Put one pointer at each end.
  3. Compare what the pair gives with the goal. Too small: move left up. Too big: move right down.
  4. Stop when you find it or the pointers meet. Each move must rule a number out for good.

Variant: Same direction

The same, but both pointers move the same way: one reads, the other marks where the next kept item goes. That rewrites the array in place, without a second array.

  1. Reach for it to filter or compact an array in place: remove duplicates or a given value, move the zeroes to the end, partition by a condition.
  2. read visits every element once. write is the index where the next kept element goes.
  3. Keep the invariant: everything left of write is the answer so far. When nums[read] passes the test, copy it to nums[write] (swap instead, if the rest must survive) and move write on.
  4. When read reaches the end, write is the length of the answer. Whatever lies from write onwards is leftover.

Variant: Two arrays

The same, but the pointers are in two different arrays, one in each. Move the one that is behind, and two sorted arrays are merged or compared in one pass.

  1. Reach for it when two sorted sequences must be walked together: merging, intersecting, comparing.
  2. Put one pointer on each sequence. Each step, compare the two items and move the pointer whose item you used.
  3. If the result goes into one of the inputs, fill it from the end where the free space is, with a third pointer that marks where to write.
  4. The same walk side by side checks whether one string is a subsequence of another: move along the long string every step, and along the short one only when the letters match.

Where it's used

  • Web search. You search for "cat dog". The search engine has two sorted lists of pages: the ones with "cat" and the ones with "dog". It puts a finger at the start of each list: the numbers match, the page fits; they do not, it moves the finger that is behind. That is how Lucene and Elasticsearch search, in one pass.
  • Databases. Orders have to be joined with customers by id. Both tables are sorted by id, so the database walks them with two pointers at once and joins rows with the same id. No order is compared with every customer. This is called a merge join.
  • Sorting. Quicksort picks a pivot, and two pointers move in from the ends: the left one looks for a number bigger than the pivot, the right one for a smaller one, and the two are swapped. After one pass the small numbers are on the left and the big ones on the right. The sort in the C++ standard library works this way.
  • The Unix comm command. It compares two sorted files and shows which lines are only in the first, only in the second, and in both. It walks the files with two pointers: the lines match, the line is shared; they do not, it moves the pointer on the smaller line.