LeetCode Meditations — Chapter 2: Two Pointers
Tags: computerscience, algorithms, typescript, javascript
Published: 2024-02-29 11:19:37

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.

![Two pointers](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nej288l6joxpn48trf80.gif)

### 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:

```ts
// 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:

![Palindrome example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bguwjnazcsdqov8hey2y.gif)

### Squares of a sorted array example

Another example where we can use the two pointers technique is the problem [Squares of a Sorted Array](https://leetcode.com/problems/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 {% katex inline %} O(n \ log \ n) {% endkatex %} runtime, so we can do it using two pointers in just {% katex inline %} O(n) {% endkatex %} time:

```ts
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 {% katex inline %} O(n) {% endkatex %}, a better runtime than {% katex inline %} O(n \ log \ n) {% endkatex %}.

The first problem we'll see in this chapter will be [Valid Palindrome](https://leetcode.com/problems/valid-palindrome), which requires a more careful approach than the simplified version shown here. 
Until then, happy coding.