977. Squares of a Sorted Array

Qustion

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

Solution

Method 1: Two pointer middle to ends

class Solution {
    public int[] sortedSquares(int[] A) {
        if(A.length == 1) return new int[]{A[0] * A[0]};
        int min = Integer.MAX_VALUE, index = -1;
        for(int i = 0; i < A.length; i++){  // O(n)
            int abs = Math.abs(A[i]);
            if(abs < min){
                index = i;
                min = abs;
            }
        }
        int left = index, right = index + 1;
        int[] result = new int[A.length];
        int count = 0;
        while(left >= 0 && right < A.length){
            if(Math.abs(A[left]) < Math.abs(A[right])){
                result[count++] = A[left] * A[left];
                left--;
            }else{
                result[count++] = A[right] * A[right];
                right++;
            }
        }
        while(left >= 0){
            result[count++] = A[left] * A[left];
            left--;
        }
        while(right < A.length){
            result[count++] = A[right] * A[right];
            right++;
        }
        return result;
    }
}

Method 2: ends to middle

class Solution {
    public int[] sortedSquares(int[] A) {
        int left = 0, right = A.length - 1;
        int[] result = new int[A.length];
        int count = A.length - 1;
        while(left <= right){
            if(A[left] * A[left] > A[right] * A[right]){
                result[count--] = A[left] * A[left];
                left++;
            }else{
                result[count--] = A[right] * A[right];
                right--;
            }
        }
        return result;
    }
}