Squares of a Sorted Array: 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 1:

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

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

Try this Problem on your own or check similar problems:

1. Merge Sorted Array
2. Sort Transformed Array

Solution:

 public int[] sortedSquares(int[] nums) {
    int[] result = new int[nums.length];
    int start = 0, end = nums.length - 1, i = nums.length - 1;
    while(start <= end){
        int squareStart  = nums[start] * nums[start];
        int squareEnd  = nums[end] * nums[end];
        if(squareStart >= squareEnd){
            result[i] = squareStart;
            ++start;
        }
        else{
            result[i] = squareEnd;
            --end;
        }
        --i;
    }

    return result;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

It’s trivial to square each number and then sort the array but that leads to O(nlog n) time complexity because of the sorting. Instead of that we can use the already ordered (sorted) nature of the input array. We utilize the two pointers approach by placing one pointer at start and the other one at the end. Note that the best candidates for the largest element in resulting array are the most negative number (start of our array) and the most positive number (end of our array), so we first compare those two. If the negative number (square of negative number is a positive number) has a larger square than the positive number (number end is pointing at) we place the square of the negative number at the end of the result array and then move our start pointer (since we used the first number, we can now go further in the array), otherwise we place a square of positive number and move our end pointer to the left. We continue this process until pointer start passes the end pointer. Notice that it is way easier to write to the resulting array end to start because of the nature of input array, if we, however would have decided to write from beginning to end to the resulting array we would have to first find the first positive number and place our second pointer to that position, and then find the smallest negative number and place our first pointer there. We would utilize the same logic of either increasing second pointer (in this case is reversed) until we reach end, or decreasing first pointer until we reach the start of input array (each time making decision based on which square is smaller).