LeetCode Meditations — Chapter 2: Two Pointers

One of the techniques of iterating through an array is the two pointers technique, and it is as simple as it sounds: we just keep two pointers, one starting from the left, and the other from the right, gradually getting closer to each other.

Palindrome example

A very basic example can be the one where we check if a string is a palindrome or not. A palindrome is a string that reads the same forwards and backwards.

In an imaginary world where all the inputs always consist of lowercase English letters, we can do it like this:

// s consists of lowercase English letters
function isPalindrome(s: string) {
  let left = 0;
  let right = s.length - 1;

  while (left <= right) {
    if (s[left++] !== s[right--]) {
      return false;
    }
  }

  return true;
}

We initialize two pointers: left and right. left points to the start of the array, while the right points to the last element. As we loop while left is less than right, we check if they are equal. If not, we return false immediately. Otherwise, our left pointer is increased; that is, it's moved to the right one step, and our right pointer is decreased, meaning that it's moved to the left one step.
When they eventually overlap, the loop terminates, and we return true.

Let's say our string is 'racecar', which is a palindrome.
It will go like this:

Squares of a sorted array example

Another example where we can use the two pointers technique is the problem Squares of a Sorted Array.

The description says:

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

For example, if the input is [-4, -1, 0, 3, 10], the output should be [0, 1, 9, 16, 100].

Now obviously, we can just square each one, and then sort the array with a built-in sort method, and be done with it. But a sorting operation is never better than $O(n \ log \ n)$ runtime, so we can do it using two pointers in just $O(n)$ time:

function sortedSquares(nums: number[]): number[] {
  let left = 0;
  let right = nums.length - 1;
  let result = [];

  while (left <= right) {
    if (Math.abs(nums[left]) > Math.abs(nums[right])) {
      result.push(nums[left++] ** 2);
    } else {
      result.push(nums[right--] ** 2);
    }
  }

  return result.reverse();
};

We compare the absolute value of the items that left and right are pointing to, and push the square of the greater one to our result array. And we return the reversed version of it.

Note
The reason we return the reversed result is that the array is initially already sorted, and we get the largest absolute value first. The reason that works is related to how two pointers work: as we start from both ends, we initially start with the smallest and largest values in the array.

Because we only make one pass through the array while comparing, and then later reversing, it ends up being $O(n)$ , a better runtime than $O(n \ log \ n)$ .

The first problem we'll see in this chapter will be Valid Palindrome, which requires a more careful approach than the simplified version shown here.
Until then, happy coding.