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)?