package sorting;
/*
(VMware) Given an array of sorted integers, return an array of the squares of each number in sorted order.
Input: [-2, 1, 2, 3]
Output: [1, 4, 4, 9]
*/
import java.util.Arrays;

public class SortSquares {

	//Two pointers, Time O(n), Space O(n), n is array length
	public static int[] sortSquares(int[] a) {
	    int n = a.length;
	    int[] res = new int[n];
	    int i = 0, j = n - 1;
	    for (int k = n-1; k >= 0; k--) {
	        if (Math.abs(a[i]) > Math.abs(a[j])) {
	            res[k] = a[i] * a[i];
	            i++;
	        } else {
	            res[k] = a[j] * a[j];
	            j--;
	        }
	    }
	    return res;
	}

	 public static void main(String[] args) {
		int[] a = {-2, 1, 2, 3};
        System.out.print("Input: ");
        System.out.println(Arrays.toString(a));
		int[] b = sortSquares(a);
		System.out.print("Sort squares: ");
		System.out.println(Arrays.toString(b));
	}
}