Community Problem
Squares of a Sorted Array
Difficulty: Easy
Return the squares of a sorted integer array, also sorted, in O(n) time using a two-pointer merge from the ends.
Squares of a Sorted Array
Return the squares of a sorted integer array, also sorted, in O(n) time using a two-pointer merge from the ends.
By @imanichen
January 27, 2026
·
Updated May 18, 2026
1,186 views
22
4.5 (11)
Showed up in a phone screen for a junior role last month and I have stolen it as my warmup ever since, because the obvious O(n log n) sort answer is the wrong one and the interviewer is patiently waiting for the candidate to realize the input is already sorted. The trick is that squaring breaks monotonicity for negative values but the largest absolute values still live at the two ends, which is exactly the setup the two-pointer merge wants.
Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number, also sorted in non-decreasing order.
Examples
Example 1:
- Input:
nums = [-4, -1, 0, 3, 10] - Output:
[0, 1, 9, 16, 100] - Explanation: After squaring,
[16, 1, 0, 9, 100], which sorts to[0, 1, 9, 16, 100].
Example 2:
- Input:
nums = [-7, -3, 2, 3, 11] - Output:
[4, 9, 9, 49, 121] - Explanation: Two of the inputs square to the same value (9). The output keeps both copies.
Example 3:
- Input:
nums = [0, 1, 2, 3] - Output:
[0, 1, 4, 9] - Explanation: All non-negative inputs already give a sorted square array.
Example 4:
- Input:
nums = [-5, -4, -3] - Output:
[9, 16, 25] - Explanation: All non-positive inputs reverse direction after squaring.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4numsis sorted in non-decreasing order.
Follow-up
The straightforward O(n log n) solution is to square every element and call sort. Can you do it in O(n) time, taking advantage of the sorted input?
Solution
Hints
Solution Walkthrough
Approach: Two-Pointer Merge from the Ends (O(n) time, O(n) output)
The naive O(n log n) solution maps every element to its square and calls a sort. The optimal O(n) solution exploits the fact that the input is already sorted: after squaring, the maximum has to come from one of the two ends because negatives flip into positive territory while positives stay positive. Compare the magnitudes at the ends, write the larger square at the back of the result, and move the winning pointer inward.
Algorithm
- Allocate
resultof lengthnand a write pointerwrite = n - 1that walks backward. - Initialize
left = 0,right = n - 1. - While
left <= right:- Compute
leftSq = nums[left]^2andrightSq = nums[right]^2. - If
leftSq > rightSq, writeleftSqatresult[write]and advanceleft. - Otherwise, write
rightSqatresult[write]and decrementright. - Decrement
write.
- Return
result.
Why It Works
Loop invariant: at the moment a value is written to result[write], it is the largest unwritten square. The unwritten squares correspond to the closed interval nums[left..right]. Squaring is monotonic on the absolute value, so the maximum magnitude in the interval sits at one of the two ends. The comparison picks the correct end, and shrinking the interval by one keeps the invariant. Writing from the back of the result means the first value written is the largest, the next is the second largest, and so on, producing a sorted output.
Complexity
Metric Value
Time O(n), each element is touched once
Space O(n) for the output arrayPitfalls
- Sorting after squaring. The O(n log n) solution works and may even be acceptable, but it ignores the sorted-input hint that this problem is built around. The two-pointer answer is what the interviewer is fishing for.
- Wrong loop bound. The loop must run while
left <= right, notleft < right, otherwise the middle element of an odd-length array never gets written. - Overflow on extreme values. With the stated constraints (
|nums[i]| <= 10^4), the maximum square is10^8, well within both languages' safe integer range. If the constraints widened to10^9, you would need to be careful in JavaScript (useBigIntor stay aware ofNumber.MAX_SAFE_INTEGER). - Mutating
numsin place. This problem allows allocating a fresh array. Trying to do it in place is significantly harder and almost never a real-world requirement.
Solution Code