977. Squares of a Sorted Array

LeetCode

If we take a look at the input array, we can easily find out that it consists of a sorted negative subarray and a sorted positive subarray. Both of the subarrays keep sorted after the elements are squared. Thus we can first square two of the subarray then use merge sort to solve this problem.

class Solution {
    public int[] sortedSquares(int[] A) {
        // corner cases
        if (A.length == 0) {
            return A;
        }
        if (A.length == 1) {
            A[0] = A[0] * A[0];
            return A;
        }

        // sets positive and negative number pointer then squares
        int neg = -1;
        int pos = A.length;
        while (pos - 1 >= 0 && A[pos - 1] >= 0) {
            pos--;
            A[pos] = A[pos] * A[pos];
        }
        while (neg + 1 < A.length && A[neg + 1] < 0) {
            neg++;
            A[neg] = A[neg] * A[neg];
        }

        // merge sort
        int[] result = new int[A.length];
        int i = 0;
        while (i < result.length) {
            if (neg < 0) {
                result[i] = A[pos];
                pos++;
            } else if (pos >= A.length) {
                result[i] = A[neg];
                neg--;
            } else if (A[neg] < A[pos]) {
                result[i] = A[neg];
                neg--;
            } else {
                result[i] = A[pos];
                pos++;
            }
            i++;
        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {-4, -1, 0, 3, 10};
        System.out.println(Arrays.toString(solution.sortedSquares(nums)));
    }
}