The following solution follows a two pointer approach and uses an additional array to store the result array in the required order. Time O(n) and space O(1) because the output array is not counted as extra space.
public int[] sortedSquares(int[] A) {
int left = 0, right = A.length-1, curr = A.length-1;
int[] B = new int[A.length];
while(left <= right){
if(Math.abs(A[left]) < Math.abs(A[right])){
B[curr--] = A[right]*A[right--];
} else {
B[curr--] = A[left]*A[left++];
}
}
return B;The below solution follows a linear approach and then sorts the array later in place. It saves space, but needs extra time for sorting. Time O(logn) and space O(1).
public int[] sortedSquares(int[] A) {
for(int i = 0; i < A.length; i++){
A[i] = A[i]*A[i];
}
Arrays.sort(A);
return A;
}Comments (1)
