Solution to Leetcode problem 977 Squares of a Sorted Array

This is the easy Leetcode problem of contest 120. In this problem, you are given a sorted array, and should return a sorted array of the squares of the values in the array.

Problem statement

The only thing that needs to be done there, apart from squaring the values, is to resort the array, because squaring negative values can reverse the order (for instance [-1, 0, 2] squared will be [1, 0, 4], and then resorted it will be [0, 1, 4]).

This can be done with the straightforward solution that follows:

class Solution {
    public int[] sortedSquares(int[] A) {
        int N = A.length;
        for (int i = 0; i < N; i++) {
            A[i] = A[i] * A[i];
        }
        Arrays.sort(A);
        return A;
    }
}

Then I wanted to do a little bit more work to obtain a linear time solution. The way it is done is by splitting the array in the middle when the sign of the values change from negative to positive (note that we could have done a simple binary search in O(ln N), but since the algorithm was going to be in linear time I didn’t do that).

Once we found the index p where the value become positive, we do the merge step from the merge-sort algorithms with subarray A[0,p] and A[p, N](second index excluded), but going through A[0,p] in reverse order.