Skip to content

LC 977. Squares of a Sorted Array

mccornet edited this page Aug 21, 2021 · 10 revisions

977. Squares of a Sorted Array

Challenge

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. 1 <= nums.length <= 104
  2. -104 <= nums[i] <= 104
  3. nums is sorted in non-decreasing order.

Solution

Pattern: two pointers

NB! output array still space O(1)

Step 1. 
    Create an empty output array, with a pointer at the end

                 *
    [_, _, _, _, _]

Step 2. 
    Pointer at the left and at the right for the input array.

     L
    [-7, -3, 2, 3, 11]
                    R

Step 3.
    - Loop over the input array, picking max(L, R)
    - Pre square the values before comparing (only in python / js, in c++ the abs() call is faster)
    - Move the pointer with the max value one step closer to the center
        and calculate the new squared value
    - Decrease the write pointer

Python

Runtime: 212 ms, faster than 85.47% of Python3 online submissions for Squares of a Sorted Array.

This is where using sort actually wins out, but as the c++ solution shows this code should be quite fast

class Solution:
    
    def sortedSquares(self, nums: list[int]) -> list[int]:
        result = [None] * len(nums)

        left_pointer = 0
        right_pointer = len(nums)-1

        # For max effeciency, pre-square the values
        # So only used values need to be recalculated
        # NB! This solution only works because python supports
        # Array wrapping!

        left_squared = nums[left_pointer] * nums[left_pointer]
        right_squared = nums[right_pointer] * nums[right_pointer] 
        
        for write_pointer in range(right_pointer, -1, -1):
            
            if left_squared > right_squared:
                result[write_pointer] = left_squared
                left_pointer += 1
                left_squared = nums[left_pointer] * nums[left_pointer]
            else:
                result[write_pointer] = right_squared
                right_pointer -= 1
                right_squared = nums[right_pointer] * nums[right_pointer]

        return result

Using abs to prevent array wrapping

class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        result = [None] * len(nums)
        left_pointer = 0
        right_pointer = len(nums)-1
        
        for write_pointer in range(right_pointer, -1, -1):
            if abs(nums[left_pointer]) > abs(nums[right_pointer]):
                result[write_pointer] = nums[left_pointer] * nums[left_pointer]
                left_pointer += 1
            else:
                result[write_pointer] = nums[right_pointer] * nums[right_pointer]
                right_pointer -= 1

        return result

Using sorted

Runtime: 196 ms, faster than 99.01%

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted([x*x for x in nums])

JavaScript

Runtime: 112 ms, faster than 85.09%

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

Just like in python using sort is also really fast

Runtime: 108 ms, faster than 93.15%

var sortedSquares = function(nums) {
    return nums.map(x => x * x).sort((a, b) => a - b)
};

C++

In C++ the two pointer solution is a lot faster than any sorting mechanism.

Runtime: 16 ms, faster than 99.71%

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) 
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);

        vector<int> res(A.size());      
        int l = 0;
        int r = A.size() - 1;
        
        for (int i = r; i >= 0; i--) {          
            if (abs(A[l]) > abs(A[r])) {
                res[i] = A[l] * A[l++];
            } else {
                res[i] = A[r] * A[r--];
            }
        }
        
        return res;
    }
};

Clone this wiki locally