DSA problem
Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
The array may contain negative numbers, so after squaring, the largest values can come from either end of the array. Solve it in O(n) time as a follow-up to the trivial sort-based approach.
Examples
Example 1
Input:
nums = [-4,-1,0,3,10]Output:
[0,1,9,16,100]Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].
Example 2
Input:
nums = [-7,-3,2,3,11]Output:
[4,9,9,49,121]Explanation: After squaring, the array becomes [49,9,4,9,121]. After sorting, it becomes [4,9,9,49,121].
Example 3
Input:
nums = [-5,-3,-2,-1]Output:
[1,4,9,25]Explanation: All values are negative; squaring reverses their order, so the smallest square comes from the rightmost element.
Constraints
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.