Loop over an array faster by using the 2-pointer technique

Yesterday I came across the “Squared of a Sorted Array” problem on Leetcode. The problem was “Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.”

What I did was, firstly, looping over the nums array to create an array of the squared of each integer, then sorting the squared array manually without using the built-in package. I used the Bubble Sort sorting algorithm because it was the only sorting algorithm I know of, haha.

func sortedSquares(nums []int) []int {
    sqrs := make([]int, len(nums))
    
    for idx, num := range nums {
        sqrs[idx] = num * num
    }
    
    n := len(sqrs)
    
    // Bubble sorting
    for i := 0; i < n; i++ {
        for j := 0; j < n-i-1; j++ {
            if sqrs[j] > sqrs[j+1] {
                sqrs[j], sqrs[j+1] = sqrs[j+1], sqrs[j]
            }
        }
    }
    
    return sqrs
}

It worked! The solution was accepted but… my code took 450 milliseconds to run which was way too long to appear in the runtime distribution chart as you can see in the image below.

I quickly jumped to the code of the most popular solution in the runtime distribution chart to see how others wrote it and this was the code:

func sortedSquares(nums []int) []int {
    left := 0
    right := len(nums) - 1
    squares := make([]int, len(nums))

    for index := right; left <= right; index-- {
        leftSquare := nums[left] * nums[left]
        rightSquare := nums[right] * nums[right]

        if leftSquare < rightSquare {
            squares[index] = rightSquare
            right--
        } else {
            squares[index] = leftSquare
            left++
        }
    }

    return squares
}

The most obvious thing contributing to the speed of the runtime was that the code above had only one for loop while mine had two main loops and one inner loop for the Bubble Sort algorithm. The time complexity of the faster code was O(n). Mine’s worst case was O(n^2) results from the Bubble Sort algorithm.

My first glance at the faster code, to be honest, I got cognitive overload! What kind of magic was that?! After spending some time trying to understand it, I finally got it!

My Explanation

A typical for loop starts from index 0, enters the loop by checking if the index is less than the length of the array, and at the end of the loop, increases the index number by one like this:

for i := 0; i < len(myArray); i++ {
    // do something
}