Sorted Squares
EasyTwo Pointers · Uber
Given an integer array nums sorted in non-decreasing order, return a new array containing the square of every value, also sorted in non-decreasing order. Keep duplicates.
Squaring and then sorting works in O(n log n); aim for O(n).
Example 1
- Input:
- nums = [-6,-2,0,3,5]
- Output:
- [0,4,9,25,36]
- Explanation
- The squares in input order are 36, 4, 0, 9, 25. Sorted, they become [0,4,9,25,36]. The largest square comes from -6 at the far left.
Example 2
- Input:
- nums = [-5,-4,-3]
- Output:
- [9,16,25]
- Explanation
- Every value is negative, so squaring reverses their order.
Example 3
- Input:
- nums = [-3,-3,2,3]
- Output:
- [4,9,9,9]
- Explanation
- -3, -3 and 3 all square to 9, and every copy is kept.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4numsis sorted in non-decreasing order