0% completed
Problem Statement
Given a sorted array, create a new array containing squares of all the numbers of the input array in the sorted order.
Example 1:
Input: [-2, -1, 0, 2, 3]
Output: [0, 1, 4, 4, 9]
Example 2:
Input: [-3, -1, 0, 1, 2]
Output: [0, 1, 1, 4, 9]
Constraints:
1 <= arr.length <= 104
-104 <= arr[i] <= 104
arr
is sorted in non-decreasing order.
Solution
We can use a brute-force approach to iterate the input array and calculate the square of each number. We can store these squares in a new array and then sort the resulting array using any sorting algorithm like Quicksort or Mergesort. Because of the sorting, this approach has a time complexity of O(N*logN), where N is the length of the input array. Here is a Python solution for this approach:
def sorted_squares(nums): return sorted([num**2 for num in nums])
Can we do better than this? Can we avoid sorting? Is it possible to generate the output in sorted order?
The tricky part is that we can have negative numbers in the input array, which makes it harder to generate the output array with squares in sorted order.
One easier approach could be to first locate the index of the first positive number in the input array. After that, we can utilize the Two Pointers technique to iterate over the array, with one pointer moving forward to scan positive numbers, and the other pointer moving backward to scan negative numbers. At each step, we can compare the squares of the numbers pointed by both pointers and append the smaller square to the output array.
For the above-mentioned Example-1, we will do something like this:
Since the numbers at both ends can give us the largest square, an alternate approach could be to use two pointers starting at both ends of the input array. At any step, whichever pointer gives us the bigger square, we add it to the result array and move to the next/previous number. Please note that we will be appending the bigger square (as opposed to the previous approach) because the two pointers are moving from larger squares to smaller squares. For that, we will be inserting the squares at the end of the output array.
For the above-mentioned Example-1, we will do something like this:
Here's a detailed walkthrough of the algorithm:
-
We start by obtaining the length of the input array,
arr
, which we store in variablen
. Then, we create a new array,squares
, of the same length to hold the squared values. We also create a variablehighestSquareIdx
and set it ton - 1
, the last index ofsquares
, which will help us populate thesquares
array from the highest (rightmost) index towards the lowest (leftmost). -
We initialize two pointers,
left
andright
, to 0 andn - 1
, respectively. These pointers represent the indices of the elements at the start (lowest) and end (highest) of the array. -
We enter a loop that continues as long as
left
is less than or equal toright
. -
In each iteration, we calculate the squares of the elements at the
left
andright
indices, storing them inleftSquare
andrightSquare
respectively. -
We then compare
leftSquare
withrightSquare
. The larger of these two squares is inserted at the position ofhighestSquareIdx
in thesquares
array, andhighestSquareIdx
is decremented. -
If
leftSquare
was larger, we incrementleft
to move towards the higher numbers in the array. IfrightSquare
was larger or equal, we decrementright
to move towards the lower numbers in the array. We're comparing absolute square values, so even if numbers in the array are negative, we're dealing with their positive square. -
This process repeats, filling up the
squares
array from right to left, untilleft
andright
meet or cross each other. -
At this point, the
squares
array is filled with the squares of the numbers in the input array, sorted in ascending order. This array is then returned as the result.
Code
Here is the code for the second approach discussed above:
Time Complexity
The above algorithm’s time complexity will be O(N) as we are iterating the input array only once.
Space Complexity
The above algorithm’s space complexity will also be O(N); this space will be used for the output array.