602. Squares of a Sorted Array
Given n integers already sorted in non-decreasing order, print the
squares of every value, themselves sorted in non-decreasing order, space
separated.
The array may contain negatives, and that is the whole difficulty. Squaring destroys the sorted order, because a large negative squares to a large positive.
Squaring and re-sorting works and costs a sort. Two pointers do it in one pass: the largest square must come from one END of the array, since the values furthest from zero sit at the extremes. Compare the two ends, take the larger square, and write results from the back of the output forwards.
Constraints - `1 ≤ n ≤ 100000` - `-100000 ≤ a[i] ≤ 100000` - The input is already sorted in non-decreasing order.
Input
The first line contains an integer n.
The second line contains n space-separated integers in non-decreasing order.
Output
Print the n squares in non-decreasing order, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.