LeetCode-in-Java
977. Squares of a Sorted Array
Easy
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
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]
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104numsis sorted in non-decreasing order.
Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?
Solution
public class Solution {
public int[] sortedSquares(int[] nums) {
int l = 0;
int r = nums.length - 1;
int[] res = new int[nums.length];
// Iterate res from back to front. put the bigger of abs(l) * abs(l) and abs(r) * abs(r) at
// res[i] and increment respectively
for (int i = nums.length - 1; i >= 0; i--) {
// If the negative is larger, put it at the end and increment left ptr to next lower
// negative
if (Math.abs(nums[l]) > nums[r]) {
res[i] = nums[l] * nums[l];
l++;
} else {
res[i] = nums[r] * nums[r];
r--;
}
}
return res;
}
}