Mastering Multiple Pointers (in Javascript)

A wildly helpful algorithm pattern

When Colt Steele first walked us through Multiple Pointers as one of the common patterns for algorithm solutions, I couldn’t lock it in straight away. But after agonizing over a problem recently others were breezing through, I was determined to acquire the tool.

The Problem

Here was the prompt:

Given two strings, one is a subsequence if all of the elements of the
first string occur in the same order within the second string. They do
not have to be contiguous in the second string, but order must be
maintained. For example, given the string ‘I like cheese’, the words (‘I’,
‘cheese’) are one possible subsequence of that string. Words are space
delimited.

Example:
s = ‘I like cheese’
t = ‘like’

function missingWords(s, t){
  // your code here
}
missingWords("I like cheese", "like")

I like cheese! Who doesn’t like cheese. No problem, right?

I’d become very comfortable at this point with creating lookup objects and while a little convoluted, this got half the tests passing. But the other half were failing. Hard. As I’m sure you know, arrays keep things in order via indexes, and here I was, missing out on that built-in assist by turning my strings into objects.

Here was one such test case throwing me for a loop:

missingWords("Python is an easy to learn powerful programming language It has efficient high-level data structures and a simple but effective approach to objectoriented programming Python elegant syntax and dynamic typing", "programming Python elegant syntax and dynamic typing")

In this instance, having the larger string to work with actually makes multiple pointers easy to understand.

Enter Multiple Pointers

The goal is to have one pointer at the beginning of our main string, and one pointer at the beginning of our sub string. Let’s get this set up first so that 1) each string is an array of words and 2) we have a result array that we will then 3) ultimately return, per the instructions:

function missingWords(s, t){
  let string = s.split(" ")
  let sub = t.split(" ")
  let result = []
  return result;
}

So, let’s set up our first pointer to be all the way left of our sub string at index 0:

let left = 0

And in the context of our loop where “i” is the index in our main string, that will be our second pointer:

let left = 0
for (let i = 0; i < string.length; i++){
  // going to do stuff here
  }
 )

Here you can visualize this:

So above you can see we’re about to have two pointers running. Let’s look at the loop:

let left = 0
for (let i = 0; i < string.length; i++){
  if (string[i] !== sub[left]){
    result.push(string[i])
   } else {
    left += 1;
   }

So the first time through we are checking, do these two words match? NO. So we will push it into the array and move on in with our iterator pointer.

Now we’re on our second time through the loop. Do they match? NO. So we will push it into the array and move on again. You can see our “left” pointer has not yet moved.

I’m going to fast forward to our first match:

So imagine we’re in our loop and we’ve just hit the else statement. These two words DO match. So we want to now move our pointer one to the right and continue on in our loop.

Let’s keep going til we hit another one:

Now we increment the left by one more and continue on in our loop. This will now take us to the end of both strings with all matches:

Here is the final code in long form:

function missingWords(s, t){
  let string = s.split(" ")
  let sub = t.split(" ")
  let result = []
  let left = 0
  for (let i = 0; i < string.length; i++){
    if (string[i] !== sub[left]){
      result.push(string[i])
    } else {
      left += 1;
    }
  return result;
 }

and with a ternary:

function missingWords(s, t){
  let string = s.split(" ")
  let sub = t.split(" ")
  let result = []
  let left = 0
  for (let i = 0; i < string.length; i++){
    string[i] !== sub[left] ? result.push(string[i]) : left += 1;
  }
 return result
}

Now that was multiple pointers at its most most basic.

Here‘s an example where you’re setting up pointers on the left and right sides of a sorted array to find the first numbers whose sums equal zero:

function sumZero(arr){
  let left = 0
  let right = arr.length - 1;
  while (left < right) {
    let sum = arr[left] + arr[right];
    if (sum === 0){
      return [arr[left], arr[right]]
    } else if (sum > 0){
      right --;
    } else {
      left ++;
    }
   }
}

Cool, right?

subZero > sumZero

Or if we’re working with strings—let’s check to see if something is a palindrome. Using multiple pointers is helpful here as well:

var isPalindrome = function(s) {
  let newString = s.replace(/[\W_]+/g, '').toLowerCase()
  let left = 0
  let right = newString.length - 1
  while (left <= right) {
    if (newString[left] !== newString[right]) return false
    left++
    right++
  }
  return true
}

Gotta love a new way to solve the palindrome question.