Squares of a Sorted Array
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. 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.
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 what makes the two-pointer technique work here.
Key Constraints:
-10^4 <= nums[i] <= 10^4→ Squaring the max magnitude gives 10^8, which fits in a signed 32-bit integer (max about 2.1 x 10^9). No overflow concerns, so plainintis safe in every language here.nums is sorted in non-decreasing order→ The ordering can be exploited to avoid sorting from scratch. This is what enables the O(n) two-pointer solution below.
Approach 1: Square and Sort
Intuition
Square every element, then sort the result. This ignores the fact that the input is already sorted, but it gives a correct baseline to improve on.
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.
The sort is the bottleneck, and it throws away the ordering the input already had. The next approach builds the squared result in sorted order directly, in O(n) time.
Approach 2: Two Pointers (Optimal)
Intuition
When a sorted array contains negative numbers, the largest squared values sit at the two 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) from the leftmost, and the smallest squares cluster near the middle, around zero.
The squared values form a U-shape: large on both ends, small in the middle. So we can place two pointers, one at each end, and compare their squares. Whichever is bigger is the next-largest value overall, so it goes into the result. We fill the result array from the back, since the largest values are found first.
Because the input is sorted, absolute values decrease as you move from each edge toward the center. The unprocessed elements always span a contiguous window [left, right], and within that window the largest square can only be at one of the two ends. So nums[left] and nums[right] are the only two candidates for the next-largest value, and comparing them picks the correct one every time.
This is the merge step from merge sort applied to two sorted runs: the negatives (squares decreasing left to right) and the non-negatives (squares increasing left to right). We merge from the largest value down, which is why the result array is filled 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.