Problem Statement

Given a sorted array, create a new array containing squares of all the numbers of the input array in the sorted order.

Example 1:

Input: [-2, -1, 0, 2, 3]
Output: [0, 1, 4, 4, 9]

Example 2:

Input: [-3, -1, 0, 1, 2]
Output: [0, 1, 1, 4, 9]

Constraints:

• 1 <= arr.length <= 10⁴
• -10⁴ <= arr[i] <= 10⁴
• arr is sorted in non-decreasing order.

Solution

We can use a brute-force approach to iterate the input array and calculate the square of each number. We can store these squares in a new array and then sort the resulting array using any sorting algorithm like Quicksort or Mergesort. Because of the sorting, this approach has a time complexity of O(N*logN), where N is the length of the input array. Here is a Python solution for this approach:

  def sorted_squares(nums):
    return sorted([num**2 for num in nums])

Can we do better than this? Can we avoid sorting? Is it possible to generate the output in sorted order?

The tricky part is that we can have negative numbers in the input array, which makes it harder to generate the output array with squares in sorted order.

One easier approach could be to first locate the index of the first positive number in the input array. After that, we can utilize the Two Pointers technique to iterate over the array, with one pointer moving forward to scan positive numbers, and the other pointer moving backward to scan negative numbers. At each step, we can compare the squares of the numbers pointed by both pointers and append the smaller square to the output array.

For the above-mentioned Example-1, we will do something like this:

Since the numbers at both ends can give us the largest square, an alternate approach could be to use two pointers starting at both ends of the input array. At any step, whichever pointer gives us the bigger square, we add it to the result array and move to the next/previous number. Please note that we will be appending the bigger square (as opposed to the previous approach) because the two pointers are moving from larger squares to smaller squares. For that, we will be inserting the squares at the end of the output array.

For the above-mentioned Example-1, we will do something like this:

Here's a detailed walkthrough of the algorithm:

1. We start by obtaining the length of the input array, arr, which we store in variable n. Then, we create a new array, squares, of the same length to hold the squared values. We also create a variable highestSquareIdx and set it to n - 1, the last index of squares, which will help us populate the squares array from the highest (rightmost) index towards the lowest (leftmost).

2. We initialize two pointers, left and right, to 0 and n - 1, respectively. These pointers represent the indices of the elements at the start (lowest) and end (highest) of the array.

3. We enter a loop that continues as long as left is less than or equal to right.

4. In each iteration, we calculate the squares of the elements at the left and right indices, storing them in leftSquare and rightSquare respectively.

5. We then compare leftSquare with rightSquare. The larger of these two squares is inserted at the position of highestSquareIdx in the squares array, and highestSquareIdx is decremented.

6. If leftSquare was larger, we increment left to move towards the higher numbers in the array. If rightSquare was larger or equal, we decrement right to move towards the lower numbers in the array. We're comparing absolute square values, so even if numbers in the array are negative, we're dealing with their positive square.

7. This process repeats, filling up the squares array from right to left, until left and right meet or cross each other.

8. At this point, the squares array is filled with the squares of the numbers in the input array, sorted in ascending order. This array is then returned as the result.

Algorithm Walkthrough

Example Input: [-2, -1, 0, 2, 3]

1. Initialization:

   • squares = [0, 0, 0, 0, 0]
   • left = 0, right = 4, highestSquareIdx = 4

2. Iteration:

   • First Iteration:
     • leftSquare = (-2)^2 = 4
     • rightSquare = 3^2 = 9
     • rightSquare > leftSquare
     • squares[4] = 9
     • Move right to 3, decrement highestSquareIdx to 3
   • Second Iteration:
     • leftSquare = 4
     • rightSquare = 2^2 = 4
     • rightSquare >= leftSquare
     • squares[3] = 4
     • Move right to 2, decrement highestSquareIdx to 2
   • Third Iteration:
     • leftSquare = 4
     • rightSquare = 0^2 = 0
     • leftSquare > rightSquare
     • squares[2] = 4
     • Move left to 1, decrement highestSquareIdx to 1
   • Fourth Iteration:
     • leftSquare = (-1)^2 = 1
     • rightSquare = 0
     • leftSquare > rightSquare
     • squares[1] = 1
     • Move left to 2, decrement highestSquareIdx to 0
   • Fifth Iteration:
     • leftSquare = 0
     • rightSquare = 0
     • squares[0] = 0
     • Move right to 1, decrement highestSquareIdx to -1

3. Result:

   • squares = [0, 1, 4, 4, 9]

Code

Here is the code for the second approach discussed above:

Complexity Analysis

Time Complexity

• Two-pointer traversal: The algorithm uses two pointers (left and right) to iterate over the input array from both ends. Each element is processed exactly once, and the pointers move toward each other until they meet.
• Constant-time operations: For each iteration, the algorithm computes the square of the element at each pointer and performs a comparison to decide where to place the squared value in the squares array. These operations are constant time, O(1).
• The loop runs N times, where N is the number of elements in the array.

Overall time complexity: O(N).

Space Complexity

• Output array: The algorithm uses an additional array squares of size N to store the squared values of the input array, resulting in a space complexity of O(N).
• In-place modification: No additional dynamic data structures are used except for the extra squares array. The other variables such as left, right, and highestSquareIdx require constant space, O(1).

Overall space complexity: O(N).