Using Two-Pointer Technique to Optimize Algorithm Solutions

#javascript #codenewbie #algorithms

When dealing with strings and arrays in the context of algorithm challenges, our first instinct usually revolves around built-in methods.

Let's take a look at this seemingly easy problem:

/* Description:
Given a sorted (ascending) array of integers, 
write a function that returns a sorted (ascending) array 
which contains the square of each number.
*/

// Examples:
square([0, 1, 2, 3, 4, 5])
// => [0, 1, 4, 9, 16, 25])

square([-7, -3, 2, 3, 11])
// => [4, 9, 9, 49, 121]

Like many others, my immediate reaction was to make use of sort() method after mapping out (map()) the squared version of each integer, like so:

function square(arr) {
  arr = arr.map(num => num * num)
  return arr.sort((a, b) => a - b)
}

While my solution above achieves the desired result, its somewhat brute-force approach leads to a not-so-performant O(n log(n)) time complexity.

So how can we improve the runtime complexity?

This is where a popular and effective strategy, Two-Pointer Technique, comes into play.

When iterating over an array or string, we can set two pointers to search and/or compare two elements. There are three common ways to set the pointers:

Start both pointers at the beginning of the iteration
Start both pointers at the end of the iteration
Start one pointer at the beginning, the other at the end, both moving toward each other and meeting in the middle.

Here's how it works in our square() example:

Step 0:

Initiate an empty array that will store our results.

Step 1:

Create two pointers, i and j, where i keeps track of the negative integers, while j keeps track of the positives.

Step 2:

Iterate over the array. Keep moving j forward until the element of the array (arr[j]) is a positive integer.

Step 3:

Inside the iteration, compare the squared elements between index i and index j, push/append the smaller element to the resulting array.

Step 4:

After the iteration in Step 3, our resulting array will have a sorted set of integers. What remains is the element(s) at index i and index j.

We can subsequently push/append the remaining elements(s) to the resulting array.

Step 5:

Return the resulting array.

Here's the two-pointer technique approach (courtesy of Women Who Code San Diego):

function squareTwoPointer(arr) {
  let result = []
  // create 2 pointers: i keeps track of negatives, j keeps track of positives
  let j = 0
  let i;

  while (j < arr.length && arr[j] < 0) {
    j++
    i = j - 1
  }

  while (j < arr.length && i >= 0) {
    if ((arr[i] * arr[i]) < (arr[j] * arr[j])) {
      result.push((arr[i] * arr[i]))
      i--
    } else {
      result.push((arr[j] * arr[j]))
      j++
    }

  }

  while (i >= 0) {
    result.push((arr[i] * arr[i]))
    i--
  }

  while (j < arr.length) {
    result.push((arr[j] * arr[j]))
    j++
  }

  return result
}

The time complexity of this optimized solution is O(n) because we only perform one iteration at a time and sort the elements in place.

As with almost all algorithm challenges, there are multiple ways to approach this problem. The two-pointer strategy appears to be a good starting point for optimization.

If you haven't applied two-pointer techniques in your problem-solving process, I hope this example boosts your confidence in coming up with more performant algorithm solutions.

Onward and upward!

Oldest comments (3)

Annie Liao • Sep 26 '20 • Edited

OK, so this approach only works when the input is sorted, as mentioned in the problem statement: "Given a sorted (ascending) array of integers, write a function that returns a sorted (ascending) array which contains the square of each number."

I know, it's not ideal, but please let me know if you have an optimized solution for an unsorted input. In any case, thanks for pointing it out and testing both functions!