A Second Pointer

A quick little post about using a second pointer when optimizing algorithms.

Unoptimized

Take a look at this function that takes an array of numbers and then returns an array of those numbers squared and sorted from smallest to largest.

function squared(array) {
    let result = []
  for (let value of array) {
    result.push(value * value)
  }


  return result.sort((a,b) => a - b)
}

This function works but it's Time Complexity isn't that great.

The For loop runs once for every element in the array so that's O(n) - a pretty fair time complexity. But then I have to run a sort, and many sort's generally time out around O(nlog(n)) - and that's basically where javascript's built-in sort method lands. That's a pretty bad result. Not much can be done about that.

But what if the initial array is already sorted? Oh, now we are getting somewhere!!

Somewhere (i.e. Optimization!)

So if the array that is sent to my function is already sorted I don't need to run sort() at all right? Well - no. If there are negative numbers in the array I still need to do some sorting.

Take this array for instance:

let unsorted = [-7, -3, 2, 3, 12]

It will give me the result [49,9,4,9,144]. That's not sorted! So how can I sort that without running sort()? That's where using a second pointer comes in.

My for loop points at one spot in the array: the current element. What if I had two pointers? One for the smallest number and one for the largest. Like so:

function squared(array) {
  let highest_pointer = array.length - 1
  let lowest_pointer = 0
  let result = []
  while (**some logic here**) {
      // some more logic here 
  }
  return result
}

So instead of a for loop we have a while loop and we are manually keeping track of each index. That way we are working our way from the beginning of the array and the end of the array.

Keep in mind our interior logic needs to include incrementing or decrementing the appropriate index whenever it adds something to the result array.

function squared(array) {
  let highest_pointer = array.length - 1
  let lowest_pointer = 0
  let result = []
  while (**some logic**) {
     if (array[lowest_pointer] ** 2 >= array[highest_pointer] ** 2) {
        result.push(array[lowest_pointer] ** 2)
        lowest_pointer++
     } else {
        result.push(array[highest_pointer] ** 2)
        highest_pointer-- 
     }  
  }
  return result
}

So what I am doing in this above example is I am checking which number is larger, the first number squared or the second one. If the array is all positive numbers it will always be the higher indexed element. But if there are negative numbers that might not be true. -7 is smaller than 3, but -7 squared is larger than 3 squared.

Once I determine which number is larger I add that to the result array and then increment (or decrement) the index.

Now: When does this loop end?

It ends when I have checked every element of the array. Or to put it another way if the lowest_pointer is pointing to a number higher than the highest_pointer. Or to put it another another way and show it as a boolean comparison:
lowest_pointer > highest_pointer
Since I am doing a while loop let's reverse that to:
while (lowest_pointer <= highest_pointer)

Let's look at the code now:

function squared(array) {
  let highest_pointer = array.length - 1
  let lowest_pointer = 0
  let result = []
  while (lowest_pointer <= highest_pointer) {
     if (array[lowest_pointer] ** 2 >= array[highest_pointer] ** 2) {
        result.push(array[lowest_pointer] ** 2)
        lowest_pointer++
     } else {
        result.push(array[highest_pointer] ** 2)
        highest_pointer-- 
     }  
  }
  return result.reverse()
}

Note that I had to reverse my results. Since I was putting the highest number first that means my array was built backwards. There wasn't an easy way to find the lowest number (without increasing my function's complexity) so I put the largest number first and then reversed it.

I could have also added the numbers into the front of the array (using unshift() vs push()) but that's actually slower than running push() and reverse(). Reverse is simply O(n) unlike sort. So running the while loop and then reverse is O(n + n) which becomes O(n) when you ignore the constant.

Read more about time complexity here.

Conclusion

When trying to optimize a function or algorithm open your mind to multiple pointers. Sometimes manually keeping track of those pointers can help you find a way to avoid some of the more complex parts of your code.