Problem statement

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

The follow-up asks for an O(n) solution — squaring then sorting is O(n log n).

Example 1

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints

• 1 <= nums.length <= 30
• -100 <= nums[i] <= 100
• nums is sorted non-decreasing.

Hints for Squares of a Sorted Array

1. Hint 1

   The largest square is at one of the two ends of the array.

2. Hint 2

   Fill the output from the back using two pointers at the ends.

How to solve Squares of a Sorted Array

Squaring destroys the sorted order only because negatives flip: the largest square is always at one end of the array, never in the middle. So compare the two ends, take the bigger square, and write it into the back of the output — filling the result right to left keeps everything ordered without a sort.

Approach

1. Put l at the first index and r at the last, and allocate an output array of the same length.
2. Fill the output from the last position backwards.
3. Compare nums[l] * nums[l] with nums[r] * nums[r].
4. Write the larger into the current output slot and move that pointer inward.
5. Continue until every slot is filled.

Why it works

The array is sorted, so absolute values decrease towards the middle from both ends and the maximum absolute value — hence the maximum square — is at l or r. Taking it and shrinking the range leaves a smaller instance of the same problem, so filling the output from the back places each value in its correct final slot. That is one pass, beating the O(n log n) of squaring and re-sorting.

Complexity

• Time — O(n)
• Space — O(n) for the output

Pitfalls

• Fill the output backwards. Writing forwards from the ends produces a descending array.
• Compare squares (or absolute values), not the raw values — -4 beats 3.
• Move only the pointer whose square you consumed.
• On a tie either side may be taken; the resulting array is the same.

Reference solution

Python

from typing import List

def sortedSquares(nums: List[int]) -> List[int]:
    n = len(nums)
    out = [0] * n
    l, r = 0, n - 1
    for i in range(n - 1, -1, -1):
        if abs(nums[l]) > abs(nums[r]):
            out[i] = nums[l] * nums[l]
            l += 1
        else:
            out[i] = nums[r] * nums[r]
            r -= 1
    return out

Java

public static int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] out = new int[n];
    int l = 0, r = n - 1;
    for (int i = n - 1; i >= 0; i--) {
        int a = nums[l] * nums[l];
        int b = nums[r] * nums[r];
        if (a > b) {
            out[i] = a;
            l++;
        } else {
            out[i] = b;
            r--;
        }
    }
    return out;
}

C++

vector<int> sortedSquares(vector<int>& nums) {
    int n = (int) nums.size();
    vector<int> out(n, 0);
    int l = 0, r = n - 1;
    for (int i = n - 1; i >= 0; i--) {
        int a = nums[l] * nums[l];
        int b = nums[r] * nums[r];
        if (a > b) {
            out[i] = a;
            l++;
        } else {
            out[i] = b;
            r--;
        }
    }
    return out;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy