LeetCode 977. Squares of a Sorted Array

Squares of a Sorted Array - LeetCode

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.

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.

Analysis

• If all elements are non-negative, their sequare value would keep the same order.
• However nums[i] could be negative, so its square value will change the order.
• Here we can use Two Pointers
  - One pointer to retrieve the number from the left
  - One pointer to retrieve the number from the right
  - Compare the abosulte value of nums[left] and nums[right] to fill result array from the end with the bigger square value

Solution

var sortedSquares = function(nums) {
    const n = nums.length;
    let left = 0;
    let right = n-1;
    const res = new Array(n);
    for (let i = n-1; i >= 0; i--) {
        if (Math.abs(nums[left]) > Math.abs(nums[right])) {
            res[i] = nums[left] * nums[left];
            left++;
        } else {
            res[i] = nums[right] * nums[right];
            right--;
        }
    }
    return res;
};