Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
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].
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?
This is a pretty fun and intuitive problem. The solution we are going to discuss essentially keeps tracking of two pointers.
The first pointer will essentially loop through the array, the pointer itself will be an index value starting at 0. If the input array at that index is less than 0, then the pointer will increment. Essentially it will either stop at 0 or the first positive number or go out of bounds.
The second pointer will be initialized at a value of one minus the first pointer.
The second pointer will either be out of bounds if there are no negative numbers, or initially holding the index value of the first negative value.
A this point in the algorithm, we will loop through the input array for as long as the first pointer is less than the length of the input array or the second pointer is greater than or equal to zero.
Since the first pointer has the potential to be pointing at the value zero, what should be evaluated is which pointer is lesser firstly and then if they are equal.
We will also be keeping an auxillary array that we'll be inserting values into.
If the first pointer is lesser, it's value at that index will be inserted and it'll be incremented. If the second pointer is lesser, it's value will be inserted and its index will be decremented.
It's important to note in the two above statements that it's possible the other pointer might be out of bounds, then in that case ALWAYS insert that pointer and increment/decrement it's index.
Finally, if they're equal at their respective indexes; simply insert both and adjust the index's value respectively.
Space: O(n)
We maintain an auxillary array that we push each the square of each index value into.
Time: O(n)
We loop through the input array once to find the first positive value and then once again in an attempt for our pointers to reach their respective ends.
A worst case would be if our input array is all negative values. In that case, the time complexity would be O(2n) which is reduced to O(n).
var sortedSquares = function(nums) {
const ascendingSquaresContainer = []
let rightIdx = 0
while (nums[rightIdx] < 0) rightIdx++;
let leftIdx = rightIdx - 1
while (leftIdx >=0 || rightIdx < nums.length) {
const leftIdxSquared = nums[leftIdx] ** 2
const rightIdxSquared = nums[rightIdx] ** 2
if (leftIdxSquared < rightIdxSquared || rightIdx >= nums.length) {
ascendingSquaresContainer.push(leftIdxSquared)
leftIdx-= 1
} else if (leftIdxSquared > rightIdxSquared || leftIdx < 0) {
ascendingSquaresContainer.push(rightIdxSquared)
rightIdx += 1
} else {
ascendingSquaresContainer.push(leftIdxSquared)
ascendingSquaresContainer.push(rightIdxSquared)
leftIdx-= 1
rightIdx += 1
}
}
return ascendingSquaresContainer
};