Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Squares of a Sorted Array

Try it yourself
EasyProblemExternal link

Description

You get an integer array nums sorted in non-decreasing order. It can hold negative numbers, zero and positive numbers.

Return a new array with the square of every number, also sorted in non-decreasing order.

Squaring is what makes this interesting: a negative number can have a bigger square than a positive one, so the squares don't come out in the same order as the numbers.

Follow-up: squaring everything and sorting takes O(n log n). Can you do it in O(n)?

Examples

Example 1

Input: nums = [-6, -2, 0, 3, 5]

Output: [0, 4, 9, 25, 36]

Explanation: Squares are 36, 4, 0, 9, 25. Sorted: [0, 4, 9, 25, 36]. The smallest square comes from 0 in the middle, not from either end.

Example 2

Input: nums = [-9, -7, -1]

Output: [1, 49, 81]

Explanation: Every number is negative, so the squares come out in reverse: 81, 49, 1 becomes [1, 49, 81].

Example 3

Input: nums = [-3, -3, 2, 3]

Output: [4, 9, 9, 9]

Explanation: Squares are 9, 9, 4, 9. Equal squares can come from both signs: three 9s, so [4, 9, 9, 9].

Constraints

  • 1 ≤ nums.length ≤ 10^4
  • -10^4 ≤ nums[i] ≤ 10^4
  • nums is sorted in non-decreasing order

Editorial

Brute Force

Intuition

The question asks for squares in order, so do exactly that: square every number, then sort the squares.

It works because sorting doesn't care where the numbers came from. It also ignores the one useful thing the problem gives us: the input is already sorted.

Step-by-Step Explanation

Let's trace nums = [-6, -2, 0, 3, 5]:

  1. Square each number, keeping their order: 36, 4, 0, 9, 25.
  2. The squares are out of order. The negative numbers at the front turned into large squares.
  3. Sort them: [0, 4, 9, 25, 36].

Square Everything, Then Sort — Each number is squared into the bottom row, then the squares are sorted.

Algorithm

  1. Create an array of the squares of nums.
  2. Sort it in non-decreasing order.
  3. Return it.

Code

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result;
        for (int x : nums) result.push_back(x * x);   // square every number
        sort(result.begin(), result.end());           // then put the squares in order
        return result;
    }
};

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        squares = [x * x for x in nums]   # square every number
        squares.sort()                    # then put the squares in order
        return squares

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) result[i] = nums[i] * nums[i];  // square every number
        java.util.Arrays.sort(result);                                         // then put them in order
        return result;
    }
}

var sortedSquares = function(nums) {
    const squares = nums.map(x => x * x);   // square every number
    // A comparator is required: the default sort compares as strings, so 100 would come before 16.
    return squares.sort((a, b) => a - b);
};

Complexity Analysis

Time Complexity: O(n log n)

Squaring is one pass, O(n). The sort is O(n log n) and dominates.

Space Complexity: O(n)

The output array holds n squares. The sort may use O(log n) to O(n) extra space depending on the language.

Why This Approach Is Not Efficient

At n ≤ 10^4 this passes easily, so the problem isn't speed here. It's that the sort repeats work the input has already done.

The numbers are already in order. Squaring only breaks that order in one predictable way: the negative numbers' squares come out in reverse. If we can use that structure instead of throwing it away, there's no need to sort at all.

This is also the follow-up interviewers ask: "the input is sorted, can you do it in O(n)?"

Optimal Approach - Two Pointers

Intuition

Where is the largest square? Not in the middle. Every number in the middle sits between nums[left] and nums[right], so its size is at most the bigger of |nums[left]| and |nums[right]|. The largest square is always at one of the two ends.

Where is the smallest square? Somewhere near zero, which could be anywhere in the middle. That's why filling the answer from the front doesn't work, and filling it from the back does.

So put a pointer at each end. Compare the two sizes, write the larger square into the last open slot of the answer, and move that pointer inward. Each step settles one slot, and the numbers between the pointers are never the largest, so nothing is skipped.

Step-by-Step Explanation

Let's trace nums = [-6, -2, 0, 3, 5]. The answer has 5 slots, filled from slot 4 down to slot 0:

  1. left = -6, right = 5. |-6| = 6 is bigger, so slot 4 gets 36. Move left.
  2. left = -2, right = 5. 5 is bigger, so slot 3 gets 25. Move right.
  3. left = -2, right = 3. 3 is bigger, so slot 2 gets 9. Move right.
  4. left = -2, right = 0. 2 is bigger, so slot 1 gets 4. Move left.
  5. left and right both point at 0, so slot 0 gets 0.

Result: [0, 4, 9, 25, 36], with five comparisons and no sort.

Two Pointers — Fill the Answer From the Back — Compare the two ends, write the larger square into the last open slot (bottom row), and move that pointer inward.

Algorithm

  1. Create a result array of length n.
  2. Set left = 0 and right = n - 1.
  3. For write from n - 1 down to 0:
    • If |nums[left]| > |nums[right]|, set result[write] = nums[left]² and move left right.
    • Otherwise set result[write] = nums[right]² and move right left.
  4. Return result.

Code

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        int left = 0, right = n - 1;
        // The largest remaining square sits at one of the two ends, so fill from the back.
        for (int write = n - 1; write >= 0; write--) {
            if (abs(nums[left]) > abs(nums[right])) {
                result[write] = nums[left] * nums[left];
                left++;
            } else {
                result[write] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
};

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        left, right = 0, n - 1
        # The largest remaining square sits at one of the two ends, so fill from the back.
        for write in range(n - 1, -1, -1):
            if abs(nums[left]) > abs(nums[right]):
                result[write] = nums[left] * nums[left]
                left += 1
            else:
                result[write] = nums[right] * nums[right]
                right -= 1
        return result

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        // The largest remaining square sits at one of the two ends, so fill from the back.
        for (int write = n - 1; write >= 0; write--) {
            if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[write] = nums[left] * nums[left];
                left++;
            } else {
                result[write] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
}

var sortedSquares = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    let left = 0, right = n - 1;
    // The largest remaining square sits at one of the two ends, so fill from the back.
    for (let write = n - 1; write >= 0; write--) {
        if (Math.abs(nums[left]) > Math.abs(nums[right])) {
            result[write] = nums[left] * nums[left];
            left++;
        } else {
            result[write] = nums[right] * nums[right];
            right--;
        }
    }
    return result;
};

Complexity Analysis

Time Complexity: O(n)

The loop runs once per slot, and each step does one comparison and moves one pointer. No sorting.

Space Complexity: O(1) extra

Besides the output array, we only keep three integers: left, right and write.

Common Mistakes

Each of these passes at least one example and still gets rejected by the tests. The outputs below come from running the code.

Stopping the loop when the pointers meet. while left < right:

On nums = [3] it returns [0]; the answer is [9]. With while left < right the loop ends when the pointers meet, so the last remaining element is never written and its slot keeps the 0 it started with.

Comparing the numbers instead of their sizes. if nums[left] > nums[right]:

On nums = [-9, 1, 2] it returns [81, 1, 4]; the answer is [1, 4, 81]. Comparing nums[left] > nums[right] asks which number is bigger, but the question is which square is bigger. -9 is smaller than 2, yet 81 is larger than 4.

Merging outward from the first non-negative number, when there isn't one. split = 0

On nums = [-9, -7, -1] it returns [81, 49, 1]; the answer is [1, 49, 81]. Finding the first non-negative index and merging outwards works, until every number is negative. The split index stays at 0, the left pointer starts at -1, and Python's nums[-1] quietly reads the last element instead of failing.