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.
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
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.