visual walkthrough
Squares of a Sorted Array
Largest values sit at the ends, so you fill the output from the back.
The idea
In a sorted array with negatives, the largest square is at the left end (a big negative) or the right end (a big positive), never in the middle. So the squares come out biggest-first from the two ends.
Fill the result from the back, comparing the two ends and moving inward: one pass, no sorting.
Complexity
| approach | time | space |
|---|---|---|
| Square, then sort | O(n log n) | O(n) |
| Two pointers | O(n) | O(n) |