Squares of a Sorted Array in JavaScript

Today, we’ll be going over a simple array problem from Leetcode. Problem number 977, which asks to return an array with the squares of each element. Let’s start.

The Prompt

Given an integer array, sorted in non-decreasing order (I don’t know why they can’t just say “ascending” order… honestly I thought it was hilarious), and return an array of the squares of each number sorted in non-decreasing order.

Conceptual Overview

Thinking about the problem at first glance, a brute force solution would be so simply traverse through the input array, square each element, and then return the final modified array. (If the interviewer didn’t want the initial array to be modified, creating another array and modifying that would be a good tactic).

An error that can come up with this would be if there are negative integers at the beginning of the array… after squaring them, these integers that were initially negative, can become larger than integers that come after. This creates the problem of an unsorted array.

A simple fix to this issue would be to sort the final array and then return it.

This brute force solution would have a time complexity of O(n log n), since we’re using a sorting function, and a space complexity of O(n) where (n) is the length of the input array.

An optimized solution would be to implement the idea of “pointers”. Let’s go over it.

Let’s assume that the input array can’t be modified.

We’ll create a new array of the same size, and fill the array with zeros. Then we’ll create two variables that will act as the pointers, one will point to the position in the array of the smaller value, and the other pointer will point to the index of the larger value.

Then, we will traverse the new array with a for loop, from RIGHT to LEFT. This way, we can be sure to insert the largest value at the ending of the new array, first.

Within the for loop, we’ll create two variables, one representing the smallest value, and the other will represent the larger value.

Then we’ll use a if/else conditional, comparing the absolute values of the smaller value variable to the larger value variable.

If the smaller value is larger than the larger value, then insert the square of the smallest value into the new array, and increment the smaller value’s index.

Else, insert the square of the larger value into the new array and decrement the larger value’s index.

Remember, the smaller value’s index and the larger value’s index, are pointers. The smaller index starts at the left-most position and increments to the right of the array. The larger index starts at the right-most position and decrements to the left of the array.

Finally, return the new array.

The Code

First create the new array and the pointers.

Now, let’s create the for loop to traverse the new array from right-to-left, and create the variables to represent the smaller and larger elements of the input array.

Once that’s taken care of, let’s implement the if/else logic. We’ll be using the absolute functionality to check absolute values of each element.

Finally, let’s return the new array.

And that’s it!

Optimized Solution Complexity Analysis

The time complexity of this solution is O(n) time, where (n) is the length of the input array.

The space complexity of this solution is O(n) space, where (n) is the size of the input array.

I hope this article helped to understand the logic behind this problem, and thank you for reading.