Squares of a Sorted Array
Given a sorted array of integers, return the squares of each number, also sorted in non-decreasing order.
Open on LeetCode ↗Intuition
You will square everything and call sort, which is O(n log n) on an array that arrived sorted — and it grates, because you can feel the input already gave you something you just threw away. The reason the linear solution is not obvious is that squaring genuinely destroys the ordering you were handed: in [-4,-1,0,3,10] the value -4 is the smallest but 16 is the second-largest square. The order is not merely disturbed, it is folded in half around zero. But notice what survives that fold: the largest magnitudes now sit at both ends of the array, and everything in between is smaller. So while you cannot read the smallest square off either end, you can always read the largest — it is whichever of the two ends squares bigger. That flips the direction of construction: compare the two ends, take the winner, and write it into the back of the result, then step that pointer inward. The invariant is that everything outside the window [l, r] has already been placed, and every value still inside it is smaller in magnitude than everything you have written so far.
The input is sorted but squaring is not monotonic — large negatives produce large squares. So the biggest square is always at one of the two ends, never in the middle. Two pointers converging inward while writing the output backwards places each value directly in its final slot.
Approach
See why the sorted input is not useless, just folded
A sorted array of signed integers is really two monotone runs glued together at zero: the negatives descend in magnitude from the left edge, the non-negatives ascend in magnitude to the right edge. Squaring is a magnitude function, so it maps this into a valley — largest at the ends, smallest somewhere in the middle. Once you picture the valley, the whole approach follows: the maximum is always at one of the two ends, and the minimum is at an interior point you would have to search for. So build from the maximum.
Compare the ends and fill the result backwards
Allocate an output array of the same length, put a left pointer at index 0, a right pointer at the last index, and a write pointer at the last output slot. Each turn, square both ends and write the larger into the write slot, then move whichever pointer you consumed one step inward and decrement the write pointer. You could compare absolute values instead of squares — same decision, and it avoids recomputing the multiplication if you care.
Run until the pointers cross
Loop while l <= r, using <= rather than < so the final single element is not dropped. Each iteration writes exactly one output slot and shrinks the window by one, so after exactly n iterations the window is empty and the output is full. Every write took the largest remaining square, so the array comes out in non-decreasing order without a single comparison sort.
Solution & live demo
Common pitfalls
Squaring then sorting
return sorted(x * x for x in nums)
while l <= r:
...
w -= 1Correct but O(n log n), discarding the sortedness the input handed you. The two-pointer sweep is O(n) because it only ever compares the two extremes.
Filling the output front-to-back
w = 0 ... w += 1
w = n - 1 ... w -= 1
The pointers identify the largest remaining square at each step, not the smallest, so results arrive in descending order. Writing backwards puts them in ascending order without a final reverse.
Comparing raw values instead of squares
if abs(nums[l]) > abs(nums[r]):
if nums[l] * nums[l] > nums[r] * nums[r]:
abs happens to work here, but comparing nums[l] > nums[r] directly does not — on [-5, 1, 3] the left value is smaller yet its square is larger. Compare the quantity you are actually ordering by.
Edge cases
The left pointer always wins, so the array is effectively reversed into the output — which is exactly right, since squaring flips the order.
The right pointer always wins and the output ends up as the input squared in place.
The squares are equal so either branch may be taken; both write the same value, so the result is identical either way.
l equals r on the first turn, one value is written, the pointers cross, and the loop ends.