sortedSquareArray

Recently been getting back into algorithms after taking a little break, and ran across the sortedSquareArray. I thought we could break this down a bit and find the best way to solve it.

Problem Statement

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Approach:

At first glance this seems simple enough, we simply just need to square each number and have that value returned in a sorted order. This technique does work, however the problem we run into is that we are not always dealing with positive numbers, we also have to consider negative numbers. We need to take in consideration any negative number squared will return a larger positive number.

Brute Force

Hack It! The easiest way to solve this is to simply take the length of our array, traverse each number and then square it. After that we can run the sort() method to put our numbers in ascending order. For example, if we were to pass [-7,-3,2,3,11] as our input, our expect output should be [4,9,9,49,121].

var sortedSquares = function(A) {
    for(let i = 0; i < A.length; i++) {
        A[i] = A[i] * A[i];       //squaring each index
    }
    const sortIndex = (a, b) => { //sort by ascending order
        return a - b;
    }
    
    return A.sort(sortIndex);  //returns [4,9,9,49,121]
};

This will give us a time complexity of O(n log n), as we can see running our sort() method is really hurting solutions in terms of time. How can we improve this by avoiding the sort() method? let’s look at a different approach using ABS.

Absolute Value

Before we look at solving this using ABS, I thought maybe we could discuss a little theory. If we were to take a number line, we can see that the smallest possible value returned is zero, so the further we get from the positive or negative side the larger the return square value will be.

With this in mind, if we were to simply create a way to compare the these values before we add them to a new array, we could avoid having to use any kind of sort() method, since we can return these numbers in ascending order after they have been compared.

Two Pointer

OK, now that we understand what we are looking to accomplish using ABS, lets look at a solutions with this in mind.

var sortedSquares = function(nums) {
  // set up new array to be retutned
  // set up our two pointers
    const result = new Array(nums.length);
    let left = 0 
    let right = nums.length - 1;
    //our loop thru to compare our two numbers and have them squared
    for (let i = nums.length - 1; i >= 0; i--) {
        if (Math.abs(nums[left]) < Math.abs(nums[right])) {
            result[i] = nums[right] ** 2
            right--;
        } else {
            result[i] = nums[left] ** 2
            left++;
        }
    }
    //return squared results in ascending order
    return result;
};

This will give a time complexity of O(n), which gives an optimal time since we can avoid having to run any sort() method on our algorithm.