Two Pointers with JavaScript

Two Pointers is a technique used for solving array and string problems. One of the benefits of using the Two Pointers technique is that the while loop will never have more than O(n) iterations. In Big O Notation, O(n) or linear complexity describes the performance of an algorithm whose run time will grow linearly and in direct proportion to the size of the input.

The Two Pointers technique consists of creating two integer variables that move along an iterable. These variables, usually named i and j, represent two indices of an array or string input. There are many different ways to implement Two Pointers. We will go over one technique in the following example.

In this example, we will reverse an array by assigning the pointers to the first and last index of the input and move them towards each other until they meet. With each iteration we will write logic to reverse the elements in the array while increasing one pointer and decreasing the other.

var arr = [‘h’, ‘e’, ‘l’, ‘l’, ‘o’]

const reverseArray = (arr) => {
  // assign the two pointers to the first and last index
  let i = 0;
  let j = arr.length-1;

  while (i < j) {
    let tmp = arr[i]; // statement 1
    arr[i++] = arr[j]; // statement 2
    arr[j--] = tmp; // statement 3
  };

  return arr;
};

First, we assign the variable ito index 0 and j to the last index of the input string arr.length-1. We use i < j for the while loop test condition. As long as this condition is true, the while loop will execute its statements. Remember that with while loops, the condition is always evaluated before the statement is executed.

For each iteration, we execute three statements:

1. Assign the tmp to arr[i]. This allows us to re-assign arr[i] in the second statement and still be able to assign arr[i]’s initial value to arr[j].
2. Assign arr[i] to arr[j] and increase i by 1
3. Assign arr[j] to tmp and decrease j by 1

The first iteration in this example swaps arr[0] (‘h’) with arr[3] (‘o’). The second iteration swaps arr[1] (‘e’) with arr[2] (‘l’) and so forth. Since we didn’t create a new array, we just need to return the modified arr which has been reversed.

In this example, the function reverseArray modifies the original array in-place giving us a space complexity of O(1). In Big O notation, O(1) space complexity or constant space means that the algorithm uses the same amount of memory regardless of the input size.