cheatsheet1999/FrontEndCollection

Squares of a Sorted Array

cheatsheet1999 opened this issue · 0 comments

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Screen Shot 2021-09-10 at 7 24 28 PM

Here is O(n) solution because the intuitive version is trivial

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    //1. We declare a result array first
    let res = [];
    //2. Put two pointers at the front and end
    let l = 0;
    let r = nums.length - 1;
    //3. Declare a special pointer 'p' for the result array only, we should make p points to the last of the array instead of 1st index, because absolute value of a negative number may become very large 
    let p = r;
    
    while(l <= r) {
        if(nums[l] ** 2 > nums[r] ** 2) {
            res[p] = nums[l] ** 2;
            l++;
            p--;
        } else {
            res[p] = nums[r] ** 2;
            r--;
            p--;
        }
    }
    return res;
    
};