Squares of a Sorted Array

Problem

You are given an integer array nums sorted in non-decreasing order, which may contain negative values. Return a new array holding the square of every element, also in non-decreasing order.

• nums has between 1 and 50,000 elements, each between -20,000 and 20,000.
• nums is sorted in non-decreasing order; it may be entirely negative or entirely non-negative.

Examples

• nums = [-6, -2, 1, 4, 9] → [1, 4, 16, 36, 81]. Squaring reorders the negatives; the -6 lands second from the right.
• nums = [-8, -5, 5, 6, 12] → [25, 25, 36, 64, 144]. -5 and 5 produce equal squares.
• nums = [2, 3, 7] → [4, 9, 49]. All non-negative, so the order is unchanged.

Hints

1. Where in the input can the largest square be located? Where can the smallest?
2. Squaring is decreasing on the negative half and increasing on the positive half, so the squares form two sorted runs.
3. Two pointers at both ends of the input; compare absolute values, write the larger square to the end of the output, and move that pointer inward.