Given an integer array nums sorted in non-decreasing order, return
an array of the squares of each number sorted in non-decreasing order.
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].
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Constraints:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums is 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?
Contents
- Solution 1 - Using two pointers
Since the input array is sorted and can contain negative integers, squaring a negative number will result in positive value,
so in this approach, first we will create an array to return the output output, and create two pointers
left and right to point at left and right end of input array nums.
Then iterate through output array length in reverse order (since highest goes on right side,
and the input array is sorted in non-decreasing order, so negative maximum will be on left end and positive maximum will be on right end of input array, so it is easy to build the output array),
and check the absolute value of left and right integers of
nums and add its square value the output array and increment left if left side element was taken, or decrement right if right side element was taken.
import java.util.Arrays;
public class SquaresOfSortedArray {
static int[] sortedSquares(int[] nums) {
int[] output = new int[nums.length];
int left =0;
int right=nums.length-1;
for(int i=output.length-1;i>=0;i--) {
if(Math.abs(nums[left]) > Math.abs(nums[right])) {
output[i] = nums[left] * nums[left];
left++;
} else {
output[i] = nums[right] * nums[right];
right--;
}
}
return output;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(sortedSquares(new int[]{-4,-1,0,3,10})));
System.out.println(Arrays.toString(sortedSquares(new int[]{-7,-3,2,3,11})));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(log n) time where n is the length of input array nums.
Space complexity: O(1).
Above implementations source code can be found at
GitHub link for Java code