Squares of a Sorted Array

How it works

This is an optimization of the previous approach that avoids the final reversal step. Instead of building the result from smallest to largest and reversing, we fill the result array from the end to the beginning. We still use two pointers to compare the absolute values at both ends, but we place each square directly in its final position.

Steps

1. Create a result array of the same size as the input.
2. Initialize l = 0, r = n - 1, and resIndex = n - 1 (pointing to the last position).
3. While l <= r:
   • Compare the absolute values of nums[l] and nums[r].
   • Place the larger square at res[resIndex] and move the corresponding pointer.
   • Decrement resIndex.
4. Return the result array (no reversal needed).

Complexity

• Time complexity: O(n)
• Space complexity: O(n) for the output array.

Things to watch for

Assuming Squares Preserve Sorted Order

A common mistake is assuming that squaring a sorted array keeps it sorted. This is false when negative numbers are present because squaring makes them positive, potentially larger than squared positive numbers. For example, [-4, -1, 0, 3] becomes [16, 1, 0, 9], which is not sorted.

Forgetting to Handle Negative Numbers with Two Pointers

When using two pointers, comparing nums[l] and nums[r] directly instead of their absolute values or squares leads to incorrect results. Negative numbers at the left end may have larger squares than positive numbers at the right end, so always compare absolute values or squared values.

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n
        l, r = 0, n - 1
        res_index = n - 1

        while l <= r:
            if abs(nums[l]) > abs(nums[r]):
                res[res_index] = nums[l] * nums[l]
                l += 1
            else:
                res[res_index] = nums[r] * nums[r]
                r -= 1
            res_index -= 1

        return res

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        int l = 0, r = n - 1, resIndex = n - 1;

        while (l <= r) {
            if (abs(nums[l]) > abs(nums[r])) {
                res[resIndex] = nums[l] * nums[l];
                l++;
            } else {
                res[resIndex] = nums[r] * nums[r];
                r--;
            }
            resIndex--;
        }

        return res;
    }
};