Squares of a Sorted Array
Last Updated: March 29, 2026
Understanding the Problem
We have a sorted array that might contain negative numbers. We need to square every element and return the result in sorted order. The tricky part is that squaring can flip the order. For example, -4 squared is 16, which is larger than 3 squared (9), even though -4 comes before 3 in the original array.
The key observation: in the original sorted array, the largest squares are at the two ends. The most negative numbers (far left) and the most positive numbers (far right) produce the biggest squares. The smallest squares are somewhere in the middle, near zero. This "U-shape" pattern in the squared values is exactly what makes the two-pointer technique work here.
Key Constraints:
1 <= nums.length <= 10^4→ With n up to 10,000, O(n^2) would mean 100 million operations, which is borderline. O(n log n) and O(n) are both comfortable.-10^4 <= nums[i] <= 10^4→ Squaring the max value gives 10^8, which fits comfortably in a 32-bit integer. No overflow concerns.nums is sorted in non-decreasing order→ This is a massive hint. Sorted input almost always means we can exploit the ordering to avoid extra work. Think two pointers or binary search.
Approach 1: Square and Sort
Intuition
The most obvious approach: square every element, then sort the result. We already know how to square numbers and how to sort arrays, so let's just combine the two.
This completely ignores the fact that the input is already sorted, which feels wasteful. But it works, and it's a clean baseline.
Algorithm
- Create a new array of the same size as
nums. - Square each element and store it in the new array.
- Sort the new array.
- Return the sorted array.
Example Walkthrough
Input:
After squaring each element:
After sorting the squared array:
Code
- Time Complexity: O(n log n). Squaring takes O(n), and sorting takes O(n log n). The sort dominates.
- Space Complexity: O(n). We create a new array of size n to hold the squared values.
This approach works but wastes the sorted order of the input by re-sorting from scratch.
Can we exploit the sorted input to build the squared result in order without needing a separate sort?
Approach 2: Two Pointers (Optimal)
Intuition
Here's the key insight: when you square a sorted array with negative numbers, the largest squared values are at the extremes. Consider [-4, -1, 0, 3, 10]. The squares are [16, 1, 0, 9, 100]. The biggest square (100) comes from the rightmost element. The second biggest (16) comes from the leftmost. The smallest squares cluster near the middle, around zero.
So the squared values form a "U-shape": big on both ends, small in the middle. This means we can use two pointers, one at each end, and compare their squares. Whichever is bigger goes into the result next. We fill the result array from the back (largest to smallest), since we're finding the largest values first.
The sorted input guarantees that absolute values decrease as you move from the edges toward the center (where the values are closest to zero). So at any point during the algorithm, the two pointers are always looking at the two candidates for the next-largest square. By comparing them and picking the bigger one, we're essentially performing a merge of two sorted sequences: the negative numbers (whose squares are sorted in decreasing order from left to right) and the positive numbers (whose squares are sorted in increasing order from left to right).
This is exactly the merge step from merge sort, except we're merging from the largest element down instead of from the smallest up. That's why we fill the result array from back to front.
Algorithm
- Initialize two pointers:
leftat the start (index 0) andrightat the end (index n-1). - Create a result array of size n.
- Fill the result array from the back (index n-1 down to 0).
- At each position, compare
nums[left]^2withnums[right]^2. - Place the larger square at the current position in the result.
- Move the corresponding pointer inward (left pointer moves right, right pointer moves left).
- Return the result array.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each element exactly once. Each iteration does O(1) work (one comparison, one assignment, one pointer move).
- Space Complexity: O(n). We need the result array of size n. If the output array doesn't count toward space, this is O(1) extra space.