Jimmy Hogerty
Jimbos1ice Development

Follow

Jimbos1ice Development

Follow
Squares of a Sorted Array

Squares of a Sorted Array

Leetcode Arrays

Jimmy Hogerty's photo
Jimmy Hogerty
·Dec 18, 2022·

2 min read

Problem Statement

Given an array of non-decreasing numbers, return a sorted, non-increasing array of each number's squared value in O(n) time. Consider the below:

//Given array
[-4,-1,0,3,10]

//Expected return value
[0,1,9,16,100]

Solution Explained

This problem deals with array traversal. In this case, we'll be traversing the given array starting at the end n[n.length - 1] and moving toward the beginning n[0].

While we move from the back of the array toward the front, we'll be constructing a new array. For each index of the new array, we'll look at the absolute value of the furthest LEFT and furthest RIGHT element.

let result = []
[-4, -1, 0, 3, 10]
  ^            ^
  4            10

Whichever is greater (10 in this case), we will set as the end of our result array at index n.length - 1 and then decrement the index to set the next element.

let result = []
[-4, -1, 0, 3, 10]
  ^            ^
  4            3

let result = [empty, empty, empty, empty, 100]

Now, we repeat this process. In this case, 4 is greater than 3. We'll now set the index of n.length - 2 to the square of 4 (i.e. 16).

let result = []
[-4, -1, 0, 3, 10]
      ^     ^
      1     3

let result = [empty, empty, empty, 16, 100]

Solution in Code

var sortedSquares = function(nums) {
    const arr = [];
    let left = 0;
    let right = nums.length - 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        const leftNum = nums[left] ** 2;
        let rightNum = nums[right] ** 2;
        if (leftNum < rightNum) {
            arr[i] = rightNum;
            right--;
        } else {
            arr[i] = leftNum;
            left++;
        }
    }
    return arr;
};
 
Share this