Skip to main content

Squares of a Sorted Array

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]

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in non-decreasing order.
Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

My solution​

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    let negIndex;
    let posIndex;
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] >= 0) {
            negIndex = i - 1;
            posIndex = i;
            break;
        } else {
            negIndex = i;
        }
    }
    
    // console.log(negIndex, posIndex)
    
    let memo = Array.from({
        length: nums.length
    })
    
    for (const index in nums) {
        const negVal = nums[negIndex] * nums[negIndex];
        const posVal = nums[posIndex] * nums[posIndex];
        
        if (!negVal || posVal < negVal) {
            memo[index] = posVal;
            posIndex++
        } else {
            memo[index] = negVal;
            negIndex--
        }
    }
    
    return memo
};