Squares of a Sorted Array — DSA · Engineering Playbook

Problem#

Given an array nums sorted in non-decreasing order (may contain negatives), return an array of the squares of each number, sorted non-decreasing.

Examples#

[-4,-1,0,3,10] → [0,1,9,16,100]
[-7,-3,2,3,11] → [4,9,9,49,121]

Constraints#

1 <= nums.length <= 10^4, -10^4 <= nums[i] <= 10^4.

Hints#

Hint 1

The largest square is at one end of the array; fill the output back-to-front.

Approach#

Two pointers at both ends. At each step, the larger absolute value is at one end. Place its square at the current back-write position and shrink that pointer. Fills the result in O(n).

Solution#

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans(n);
        int l = 0, r = n - 1, k = n - 1;
        while (l <= r) {
            if (abs(nums[l]) > abs(nums[r])) {
                ans[k--] = nums[l] * nums[l];
                ++l;
            } else {
                ans[k--] = nums[r] * nums[r];
                --r;
            }
        }
        return ans;
    }
};

func sortedSquares(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    l, r, k := 0, n-1, n-1
    abs := func(x int) int {
        if x < 0 {
            return -x
        }
        return x
    }
    for l <= r {
        if abs(nums[l]) > abs(nums[r]) {
            ans[k] = nums[l] * nums[l]
            l++
        } else {
            ans[k] = nums[r] * nums[r]
            r--
        }
        k--
    }
    return ans
}

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        l, r, k = 0, n - 1, n - 1
        while l <= r:
            if abs(nums[l]) > abs(nums[r]):
                ans[k] = nums[l] * nums[l]
                l += 1
            else:
                ans[k] = nums[r] * nums[r]
                r -= 1
            k -= 1
        return ans

function sortedSquares(nums) {
    const n = nums.length;
    const ans = new Array(n);
    let l = 0, r = n - 1, k = n - 1;
    while (l <= r) {
        if (Math.abs(nums[l]) > Math.abs(nums[r])) {
            ans[k--] = nums[l] * nums[l];
            l++;
        } else {
            ans[k--] = nums[r] * nums[r];
            r--;
        }
    }
    return ans;
}

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int l = 0, r = n - 1, k = n - 1;
        while (l <= r) {
            if (Math.abs(nums[l]) > Math.abs(nums[r])) {
                ans[k--] = nums[l] * nums[l];
                l++;
            } else {
                ans[k--] = nums[r] * nums[r];
                r--;
            }
        }
        return ans;
    }
}

function sortedSquares(nums: number[]): number[] {
    const n = nums.length;
    const ans: number[] = new Array(n);
    let l = 0, r = n - 1, k = n - 1;
    while (l <= r) {
        if (Math.abs(nums[l]) > Math.abs(nums[r])) {
            ans[k--] = nums[l] * nums[l];
            l++;
        } else {
            ans[k--] = nums[r] * nums[r];
            r--;
        }
    }
    return ans;
}

Editorial#

The naïve “square then sort” is O(n log n). Exploiting the sorted-ish structure (sorted by value, but |x| is a U-shape) gives O(n): since the original is sorted by value, the largest |x| is always at one of the two ends. Filling back-to-front avoids any shifting.

Complexity#

Time: O(n).
Space: O(n) for output.

Concept revision#

Sort Colors

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#