Return sorted squares of a sorted array

## Problem You are given an integer array `nums` sorted in **non-decreasing** order. The array may contain negative numbers. Return a new array containing the **square of each number**, also sorted in **non-decreasing** order. ## Input - `nums`: an array of integers sorted in non-decreasing order. ## Output - An array of integers representing the squares of `nums`, sorted in non-decreasing order. ## Constraints (typical interview scale) - `1 <= nums.length <= 10^5` - `-10^4 <= nums[i] <= 10^4` ## Examples - Input: `nums = [-4, -1, 0, 3, 10]` Output: `[0, 1, 9, 16, 100]` - Input: `nums = [-7, -3, 2, 3, 11]` Output: `[4, 9, 9, 49, 121]` ## Follow-up Can you solve it in **O(n)** time (better than sorting after squaring)?