Squares of a Sorted Array Solution

Problem

You're given an array of integers sorted in non-decreasing order (including negatives). Return a new array containing the square of each number, also in non-decreasing order.

Input: nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
Explanation: Squaring gives [16, 1, 0, 9, 100]; sorted, that's [0, 1, 9, 16, 100]

Counter-example showing why you can't just square left-to-right: [-7, -3, 2, 4] → squares are [49, 9, 4, 16], which is neither sorted nor trivially fixable without a comparison step.

Intuition

After squaring, large values can come from either end of the array — the most negative numbers and the most positive numbers both produce large squares. So instead of squaring and re-sorting, we can use two pointers starting at opposite ends, always picking the larger square and placing it at the back of the result array. This fills the answer from largest to smallest in a single pass.

Approach 1 — Sort After Squaring

Square every element, then sort. Simple and correct, but pays the O(n log n) cost of sorting even though the input was already in a useful order.

Build a new array by squaring each element.
Sort the squared array and return it.

1def sortedSquares(nums: list[int]) -> list[int]:
2    return sorted(x * x for x in nums)

Time: O(n log n) — dominated by the sort step.

Space: O(n) — the output array.

Approach 2 — Two Pointers (Optimal)

The largest square at any moment is always at one of the two ends of the remaining input range. Use left and right pointers that move inward, placing the larger square at the back of the result array and working toward the front.

Initialize left = 0, right = n - 1, write_index = n - 1.
While left <= right:
- Compute left_sq = nums[left]² and right_sq = nums[right]².
- Place the larger of the two at result[write_index] and advance the corresponding pointer inward.
- Decrement write_index.
Return result.

1def sortedSquares(nums: list[int]) -> list[int]:
2    n = len(nums)
3    result = [0] * n
4    left, right = 0, n - 1
5    write_index = n - 1
6
7    while left <= right:
8        left_sq = nums[left] * nums[left]
9        right_sq = nums[right] * nums[right]
10        if left_sq >= right_sq:
11            result[write_index] = left_sq
12            left += 1
13        else:
14            result[write_index] = right_sq
15            right -= 1
16        write_index -= 1
17
18    return result

Time: O(n) — each element is visited exactly once.

Space: O(n) — the output array; no extra structures needed.

Complexity Summary

Approach	Time	Space	When to use
Sort After Squaring	O(n log n)	O(n)	When brevity matters and performance is not critical
Two Pointers	O(n)	O(n)	Always when you want the optimal solution

Common Mistakes

Filling the result from the front instead of the back — if you pick the largest square and write it to result[0], you'd need to shift everything; writing from the back avoids this entirely.
Using left < right instead of left <= right — when both pointers converge on the same element (e.g., a single middle element), left < right exits too early and skips that element.
Forgetting that squaring a negative makes it positive and potentially large — it's tempting to assume the sorted order of absolute values follows the input order, but -7 has a larger square than 3 even though it's earlier in the array.
Comparing the raw values instead of their squares — the pointers should compare nums[left]² vs nums[right]², not abs(nums[left]) vs abs(nums[right]). Both are equivalent, but computing the square directly avoids an extra function call and makes the intent clear.
Integer overflow in Java/C++ for large inputs — squaring a 32-bit integer at its boundary (±46341) overflows int. In practice LeetCode's constraints keep values within safe range, but in production code consider using long for intermediate results.

Squares of a Sorted Array — Solution