Squares of a Sorted Array — Merge from the Outside at Google and Bloomberg

Problem Statement#

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

Constraints:

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

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

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

Why This Problem Matters#

LeetCode 977 Squares of a Sorted Array is a Google favorite because it tests whether candidates can recognize that squaring breaks the sort order in a structured way, then exploit that structure for an O(n) solution. The naive solution squares every element and re-sorts, costing O(n log n). The two pointer solution runs in O(n) and is what Google, Bloomberg, and Amazon expect.

The trick is realizing that the largest squares come from either the most-negative or the most-positive element, not from the middle. Once you see that, the merge-from-outside strategy falls out naturally.

This problem also teaches the pattern of writing into the output array from the back, a technique that reappears in LC 88 Merge Sorted Array and LC 283 Move Zeroes follow-ups.

The Core Insight#

After squaring, negative numbers become positive and the sort order can flip. The smallest absolute value sits somewhere in the middle, while the largest absolute values are at the two ends.

Two pointers, one at the left end and one at the right end, always reference the two largest remaining absolute values. Compare their squares, write the larger one into the back of the output, and move that pointer inward. Repeat until the pointers cross.

Writing from the back of the output array is essential because we are emitting largest-first while the output must be sorted smallest-first.

Visual Dry Run#

For input nums = [-4, -1, 0, 3, 10], output index starts at 4:

Solution (Optimal)#

class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [0] * n
        left, right, write = 0, n - 1, n - 1
        while left <= right:
            left_sq = nums[left] * nums[left]
            right_sq = nums[right] * nums[right]
            if left_sq > right_sq:
                result[write] = left_sq
                left += 1
            else:
                result[write] = right_sq
                right -= 1
            write -= 1
        return result

var sortedSquares = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    let left = 0;
    let right = n - 1;
    let write = n - 1;
    while (left <= right) {
        const leftSq = nums[left] * nums[left];
        const rightSq = nums[right] * nums[right];
        if (leftSq > rightSq) {
            result[write] = leftSq;
            left++;
        } else {
            result[write] = rightSq;
            right--;
        }
        write--;
    }
    return result;
};

Time: O(n) — single pass with two pointers Space: O(n) — output array, no auxiliary buffers beyond it

Common Mistakes#

• Squaring everything first then calling sort, costing O(n log n) and missing the point
• Writing from the front of the output array, which forces a final reversal
• Using left < right instead of left <= right and missing the middle element on odd-length input
• Comparing absolute values instead of squares, which works but is slightly slower in some languages
• Forgetting that input may contain duplicates or zeros, which the merge handles naturally

Interview Tips#

• State the brute force first: "We could square and sort in O(n log n), but the input is already sorted so we should be able to do better"
• Draw arrows from both ends to show the merge-from-outside intuition
• Walk through an example with mixed signs and a zero to demonstrate edge case handling
• Mention that this is structurally identical to merging two sorted arrays, where the two arrays are the negatives reversed and the non-negatives

Follow-up Questions#

• What if the array is not sorted? (Hint: O(n log n) is optimal, just sort the squares)
• What if you can only output positives? (Hint: filter then square or square then filter)
• How would you do this with a stream where you cannot index from the back? (Hint: deque or two queues)
• Generalize to cubes of a sorted array. (Hint: cubes preserve sign, so a single-pointer scan works)
• What if the array is sorted in non-increasing order? (Hint: same logic, swap pointer directions)

Key Takeaways#

• LeetCode 977 Squares of a Sorted Array tests whether you can beat the obvious O(n log n) approach
• Squaring breaks sort order only at the boundary between negatives and positives
• The largest squares always come from one of the two ends, never the middle
• Two pointers from opposite ends with a back-to-front write index achieve O(n) time and O(n) space
• Write from the back of the output array to avoid a final reversal step
• Use left <= right to handle odd-length arrays correctly
• The pattern generalizes to LC 88 Merge Sorted Array and other merge-from-outside problems