Two Pointer Technique and Arrays, Part 1

The two pointer technique is very useful to understand for solving array problems efficiently.

To use the two pointer technique we use pointers to keep track of indices of an array, string or linked list. Today I am talking about the implementation for arrays.

A pointer is defined as a reference to an object. To use this technique we declare two local variables to use as pointers. We can use the pointers to explore two elements in an array at the same time, in contrast to using a nested loop to do the same.

There are three main approaches that I want to go over to get started that don’t overlap with other more specific techniques.

1. Left/Right: One pointer starts at the beginning of the array and the other at the end. They move one at a time until they meet.
2. Fast/Slow: One pointer moves faster than the other.
3. Two Sequences: Each pointer represents the current position in the corresponding sequence.

The two pointer technique can be extended to more advanced techniques such as sliding window and dynamic programming.

The uses for two pointer are searching for pairs in a sorted array, array transformation or comparing two arrays to each other.

The benefit of using a two pointer solution is that it improves on the brute force solution to comparing elements of an array to all other elements of that same array by using a nested loop (or multiple).

Approach 1: pointers at the beginning and end of an array

This approach is useful for searching for pairs in an array. Let’s look at the classic Two Sum problem that I wrote about previously here. This problem is the perfect candidate for pointers:

Given an array of integers nums and an integer target, return an array with the two integers that add up to the target in any order..

There will be at most one solution. If no solution exists, return an empty array.

Solution

function twoNumberSum(array, targetSum) {
  array.sort((a,b) => a-b)
 
  let leftIdx = 0;
  let rightIdx = array.length - 1;
 
  while (leftIdx < rightIdx) {
    if (array[leftIdx] + array[rightIdx] === targetSum) {
      return [array[leftIdx], array[rightIdx]];
    } else if (array[leftIdx] + array[rightIdx] < targetSum) {
      leftIdx++;
    } else {
      rightIdx--;
    }
  }
 
 return [];
}

Steps:

• In this case, the input array is not necessarily sorted so we sort it. This techniques relies on a sorted array. Because the .sort method in JavaScript is destructive we can do so in place (assuming it is okay to mutate the original array. If not, we can make a copy first).
• We declare a local variable for the first index and set it equal to 0 and declare a local variable or the last index and set it equal to the array’s length minus 1.
• While the left index is smaller than the right index, we check to see if our 2 candidates (the numbers at those indices) are a match. If so, we return them. If the sum of the candidates is smaller than the target, we increase the left index. This is because we need our sum to be larger, and since the array is sorted increasing the left index will get us a larger number. If the sum is larger than the target, we decrease the right index.
• If the left and right indices cross each other (the left index is larger than or equal to the right) then we have explored every number and return an empty array.

The time complexity of this solution is O(nlogn) compared to the brute force O(n²) (a nested loop). This is because had to sort the input array. If we did not have to sort the time complexity would be O(n).

The space complexity is O(1).

Approach 2: one pointer moves faster than the other

This approach is typically used for linked lists but can also be useful for array transformation problems.

To implement this approach on an array, typically we declare a local variable and set it equal to 0, and then loop through the array. The variable acts as one pointer and the index of the loop acts as the second.

This can be used to solve problems such as removing duplicates from an array or moving elements in an array.

Let’s look at the Move Zeros problem on Leetcode:

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Let’s check out a two pointer solution:

var moveZeroes = function(nums) {
    let leftIdx = 0;
    
    for (let i=0; i<nums.length; i++) {
        if (nums[i] !== 0) {
            if (leftIdx === i) {
                leftIdx++
                continue;
            }
            nums[leftIdx] = nums[i];
            nums[i] = 0;
            leftIdx++
        }
    }
};

Steps:

• Declare a local variable for the first index and set it equal to 0.
• Loop through the array, the index of the iteration is our second pointer.
• When we encounter a 0, our first pointer (here called leftIdx) will keep track of the index. The other pointer continues. When we encounter a number that is not 0, we swap the numbers using the 2 pointers and move the left pointer. When the loop completes, all the zeros will be moved to the end.
• Until we encounter the first zero, we can move both pointers and take no further action (what this block of code is doing: if(leftIdx === i)).

This solution optimizes for both time (O(n) time) and space (O(1) space).

Next post

I talk about the approach involving 2 sequences on the next post in this series.