Description:

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.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Brute Force

In brute force approach, we can square each of the numbers and then sort them in non-decreasing, i.e. ascending order.

1for element in nums
2    nums[i] = nums[i] * nums[i]
3sort nums array

The brute force approach would look like this. In this case, we can also implemented our own sorting algorithm as a function. However, the best time complexity for sorting algorithm is O(n log n). So, our overall solution can never be better than O(n log n) with this algorithm.

 1class Solution {
 2    public int[] sortedSquaresBrute(int[] nums) {
 3        int[] result = new int[nums.length];
 4
 5        // find squares
 6        for(int i = 0; i < nums.length; i++) {
 7            result[i] = nums[i] * nums[i];
 8        }
 9        // sort the array
10        Arrays.sort(result);
11
12        return result;
13    }
14}
  • Time Complexity: O(n log n)
  • Space Complexity: We are using a result array of the same size as the input array. So, in this case, space complexity is O(n).

Better Solution:

 1two pointers approach
 2left = 0, right = nums.length - 1, i = nums.length - 1
 3Initialize result array with same size as nums to store sorted result
 4while (left < right)
 5    if (square of nums[left] greater than square of nums[right])
 6        result[i] = square of nums[left]
 7        left++
 8        i--
 9    else
10        result[i] = square of nums[right]
11        right--
12        i--
13return result

The implemention for above algorithm will look like this.

 1class Solution {
 2    public int[] sortedSquares(int[] nums) {
 3        int[] result = new int[nums.length];
 4
 5        int left = 0, right = nums.length - 1;
 6        int i = nums.length - 1;
 7
 8        while (left < right) {
 9            if (nums[left] * nums[left] > nums[right] * nums[right]) {
10                result[i--] = nums[left] * nums[left];
11                left++;
12            } else {
13                result[i--] = nums[right] * nums[right];
14                right--;
15            }
16        }
17
18        return result;
19    }
20}
  • Time Complexity: O(n)
  • Space Complexity: O(n)