574. Squares of a Sorted Array
You are given an integer array nums that is already sorted in non-decreasing order, but it may contain negative values. Return a new array holding the square of every element, also sorted in non-decreasing order.
Squaring breaks the ordering wherever negatives appear — -7 comes before 2, yet 49 belongs after 4 — so the challenge is to restore sorted order. Sorting after squaring is the obvious fix; the follow-up is to produce the result in a single O(n) pass by exploiting the fact that the input is already sorted.
Example 1:
Input: nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
Explanation: Squaring gives [16, 1, 0, 9, 100]; reordering yields [0, 1, 9, 16, 100].
Example 2:
Input: nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Explanation: The squares are [49, 9, 4, 9, 121]; sorted they become [4, 9, 9, 49, 121].
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- -10⁴ ≤ nums[i] ≤ 10⁴
- nums is sorted in non-decreasing order
Hints:
After squaring, where do the biggest values live? Only at the two ends of the original array — the most negative and the most positive elements.
Compare the squares at both ends, write the larger one into the LAST open slot of the output, and step that end inward. Fill the result from the back to the front.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [-4, -1, 0, 3, 10]
Expected output: [0, 1, 9, 16, 100]