Squares of a sorted array

Square every value of a sorted array and keep the result sorted. The largest square is always at one of the two ends, so fill the answer from the back.

The idea

Squaring turns a sorted array with negatives into a valley: the squares fall towards the value nearest 0 and rise again on both sides. So the biggest remaining square is always at the left end or the right end. Compare the two ends, write the bigger square into the last free slot of the result, and move that pointer inward. Every slot is decided in one comparison.

Code

public int[] SortedSquares(int[] nums) {
    int n = nums.Length, l = 0, r = n - 1;
    var result = new int[n];
    for (int pos = n - 1; pos >= 0; pos--) {
        int a = nums[l] * nums[l], b = nums[r] * nums[r];
        if (a > b) { result[pos] = a; l++; }
        else { result[pos] = b; r--; }
    }
    return result;
}

Tips

• Fill from the back: the ends give the largest squares, not the smallest. Starting from the front would mean first finding the value closest to 0.
• Ties can go either way; this code takes the right end.
• Squaring and then calling Array.Sort also works, in O(n log n). The two pointers make it O(n).

In the .NET library

Array.Sort would be the one-line O(n log n) answer. Two pointers avoid it, and allocating result once with new int[n] keeps the loop free of List<T> resizing.