Multiple Pointers Pattern

Before delving into classic algorithms and data structures, we must learn or revisit some problem-solving patterns. The Multiple Pointers pattern will be our starting point.

The main idea here is to create multiple pointers attached to specific positions and move them based on a particular condition.

You can find Multiple Pointers In countless algorithms, like:

• Binary Search

• Quick Sort

• Merge Sort

• Etc.

Let's imagine we need to write a function that finds the first pair where the sum is 0 from a given SORTED array. E.g., [-5, -1, 0, 2, 5] //-5 + 5

Instinctively, we write something like the following:

function pairSum(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (arr[i] + arr[j] === 0) return `${arr[i]} + ${arr[j]}`;
        }
    }
}

The big problem here is that our time complexity is quadratic O(n^2) because we walk through the array twice. But, we can solve it by using Multiple Pointers to walk through the array only once:

function pairSum(arr) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === 0) {
      return `${arr[left]} + ${arr[right]}`;
    } else if (sum < 0)   
 {
      left++;
    } else {
      right--;
    }
  }

  return null;
}

Now, we have a linear time complexity O(n).

Let's get deeper into the above solution:

• We set up two pointers: left with the initial position and right with the last position.

• The loop will be running until left < right.

• We store the first sum.

• If sum === 0, we found our pair.

• If not and sum < 0, we will move our left pointer to the right by incrementing it.

• If sum > 0, move the right pointer to the left by decrementing it.

• If nothing was found, return null.

Let's suppose we have the following SORTED array:

[-6, -5, -1, 0, 2, 3, 4, 5, 10]

1.
[-6, -5, -1, 0, 2, 3, 4, 5, 10]
  ^                          ^
 left                      right

 sum = -6 + 10 = 4

 As 4 > 0, we move our right pointer to the left

 [-6, -5, -1, 0, 2, 3, 4, 5, 10]
   ^                      ^
 left                   right

 sum = -6 + 5 = -1

 -1 < 0, we move the left pointer to the right

 [-6, -5, -1, 0, 2, 3, 4, 5, 10]
       ^                  ^
      left              right

sum = -5 + 5 = 0

Pair found: -5, 5.