[Google Question] Sort squares of a Sorted Array

Problem: Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example:

Input: nums = [-3,-2,0,1,4]
Output: [0,1,4,9,16]
Explanation: After squaring, the array becomes [9,4,0,1,16]. After sorting, it becomes [0,1,4,9,16].

Approach: A trivial approach will be to first square every element  and then sort the array. This will take O(nlogn) time obviously for sorting. Let's try to do better.

The intuition is that largest square value could be one of the following values:

1. Square of the largest positive number.
2. Square of the lowest negative number.

It is obvious that lowest negative number will be the first one in the array and largest positive number will be the last one in the array so with this intuition we can apply two pointers approach: One from the end and one from start, whichever number's absolute value is greater, we put its square from the end of the result array.

Now we just need to move these pointers according to which value we have used. That's all.

Implementation in C#:

    public int[] SortedSquares(int[] nums) 

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return nums;

        }

        int[] result = new int[length];

        int low = 0, high = length - 1;

        int writeIndex = length - 1;

        while (low <= high)

        {

            if (Math.Abs(nums[low]) < Math.Abs(nums[high]))

            {

                result[writeIndex--] = nums[high] * nums[high];

                --high;

            }

            else

            {

                result[writeIndex--] = nums[low] * nums[low];

                ++low;

            }

        }

        return result;

    }

Complexity: O(n)