LeetCode 977 - Squares of a Sorted Array

https://leetcode.com/problems/squares-of-a-sorted-array/

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. 1 <= A.length <= 10000
2. -10000 <= A[i] <= 10000
3. A is sorted in non-decreasing order.

X. Two pointers

https://leetcode.com/problems/squares-of-a-sorted-array/discuss/221922/Java-two-pointers-O(N)
https://leetcode.com/problems/squares-of-a-sorted-array/discuss/221924/C%2B%2BJava-4-lines-O(n)-inside-out-or-outside-in

In a way, we are going inside out and filling our result vector from the beginning. Alternativelly, we can go outside in and fill the result in the reverse order:

    public int[] sortedSquares(int[] A) {
        int n = A.length;
        int[] result = new int[n];
        int i = 0, j = n - 1;
        for (int p = n - 1; p >= 0; p--) {
            if (Math.abs(A[i]) > Math.abs(A[j])) {
                result[p] = A[i] * A[i];
                i++;
            } else {
                result[p] = A[j] * A[j];
                j--;
            }
        }
        return result;
    }




public int[] sortedSquares(int[] A) {
  int[] res = new int[A.length];
  for (int pn = 0, pp = A.length - 1, pos = A.length - 1; pn <= pp; --pos)
    res[pos] = (int)Math.pow(Math.abs(A[pn]) < Math.abs(A[pp]) ? A[pp--] : A[pn++], 2);
  return res;
}




Since the array A is sorted, loosely speaking it has some negative elements with squares in decreasing order, then some non-negative elements with squares in increasing order.

For example, with [-3, -2, -1, 4, 5, 6], we have the negative part [-3, -2, -1] with squares [9, 4, 1], and the positive part [4, 5, 6] with squares [16, 25, 36]. Our strategy is to iterate over the negative part in reverse, and the positive part in the forward direction.

  public int[] sortedSquares(int[] A) {

    int N = A.length;

    int j = 0;

    while (j < N && A[j] < 0)

      j++;

    int i = j - 1;

    int[] ans = new int[N];

    int t = 0;

    while (i >= 0 && j < N) {

      if (A[i] * A[i] < A[j] * A[j]) {

        ans[t++] = A[i] * A[i];

        i--;

      } else {

        ans[t++] = A[j] * A[j];

        j++;

      }

    }

    while (i >= 0) {

      ans[t++] = A[i] * A[i];

      i--;

    }

    while (j < N) {

      ans[t++] = A[j] * A[j];

      j++;

    }

    return ans;

  }

  public int[] sortedSquares(int[] A) {

    int N = A.length;

    int[] ans = new int[N];

    for (int i = 0; i < N; ++i)

      ans[i] = A[i] * A[i];

    Arrays.sort(ans);

    return ans;

  }