Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number, also sorted in non-decreasing order.
Squaring and then sorting takes O(n log n). Can you do it in O(n)?
Examples
Example 1
- Input
- nums = [-4, -1, 0, 3, 10]
- Output
- [0, 1, 9, 16, 100]
Example 2
- Input
- nums = [-7, -3, 2, 3, 11]
- Output
- [4, 9, 9, 49, 121]
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4numsis sorted in non-decreasing order.