Solve Squares of Sorted Array in O(N)

417

The given array is sorted. We can use that to construct sorted squares array. Do the following

Use the two pointer approach. One pointer is called neg which will track negative numbers. And other is called pos tracking positive numbers.
One key thing to note here is that neg will move from right to left. And pos will move from left to right.
Find the correct index for neg which will be the index of last negative number. And pos will be neg+1;
Now at each iteration compare the squares of numbers at index neg and pos. And whichever is lowest, put that in the result array. And increment/decrement the correct pointer. neg will be decremented and pos will be incremented.
Make sure to take care of edge cases where there are no negative or positive numbers.

Code as follows (try to solve it yourself first)

class Solution {
    public int[] sortedSquares(int[] A) {
        int n = A.length;
        int[] squares = new int[n];
        int firstPos = 0;
        for(int i=0;i<n;i++){
            if(A[i] >= 0){
                firstPos = i;
                break;
            }
        }
        int i = firstPos;
        int j = firstPos-1;
        if(i == -1){
           j= n-1;
           i = n;
        }
        int k = 0;
        while(i < n || j >= 0){
            int iVal = i < n ? Math.abs(A[i]) : Integer.MAX_VALUE;
            int jVal = j >= 0 ? Math.abs(A[j]) : Integer.MAX_VALUE;
            int min = 0;
            if(iVal < jVal) {
                min = iVal;
                i++;
            }else {
                min = jVal;
                j--;
            }
            squares[k++] = min*min;
        }
        return squares;
    }
}

Comments (0)