Squares of a Sorted Array

Problem

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.

Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    let split = 0; // index of first non-negative value
    for (; split < nums.length && nums[split] < 0; split++);

    let left = split - 1; // index for negative elements
    let right = split; // index for non-negative elements
    const res = [];

    for (let i = 0; i < nums.length; i++) {
        const val1 = Math.abs(nums[left] ?? Infinity);
        const val2 = Math.abs(nums[right] ?? Infinity);

        if (val1 < val2) {
            res.push(val1 ** 2);
            left--;
        } else {
            res.push(val2 ** 2);
            right++;
        }
    }

    return res;
};

We will implement a two pointers solution. Since nums is sorted in non-decreasing order, the abs of the negative values will increase as we move to the left of nums, while the positive values will increase as we move to the right of nums. Thus, we find the index split of where the values in nums changes from negative to positive, and slide outwards. Note that it might be more performant to slide inwards instead of outwards (ie. square the larger values first instead of the smaller values), as this avoids the need to compute split.