# 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.

## Problem Statement

Given an integer array `nums` sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. In other words, the task is to square each element in the array and then return a new array that contains the squares of each element, sorted in non-decreasing order.

## Examples

```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].```
```Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]```

## Clarifying Questions

1. Can the input array contain negative numbers, or will it always be non-negative?
2. Can the input array contain duplicate numbers?
3. Can I modify the input array, or should I create a new one for the output?
4. Is there any time or space complexity constraint that I need to consider?

## Solutions

There are multiple approaches to solving the problem of computing the squares of sorted array elements:

### Sorting the squared array:

We can square each number in the input array, sort the squared array, and then return it. This approach has a time complexity of O(n log n) due to the sorting algorithm used.

#### Algorithm:

1. Square each number in the input array.
2. Sort the squared array using a sorting algorithm.
3. Return the sorted squared array.

Time complexity: O(nlogn), where n is the length of the input array. This is because we need to sort the array after squaring each element.

Space complexity: O(n), where n is the length of the input array. This is because we need to store the squared elements in a separate array.

### Two-pointer approach:

We can use a two-pointer approach where we use two pointers, one at the beginning and one at the end of the array, and compare the squares of the two elements pointed to by the pointers and add the larger square to a result array from the end. Then move the pointer pointing to the larger element towards the middle of the array. Repeat this process until both pointers meet in the middle of the array. This approach has a time complexity of O(n).

#### Algorithm:

1. Initialize two pointers, one at the beginning and one at the end of the input array.
2. Initialize an empty output array.
3. While the two pointers have not crossed each other, compare the squares of the numbers at the two pointers.
4. Insert the larger squared number into the output array and move the corresponding pointer accordingly.
5. Continue until both pointers have crossed each other.
6. If there are any remaining numbers to be squared in the input array, square and add them to the output array.
7. Return the output array.

Time complexity: O(n), where n is the length of the input array. This is because we traverse the array once with two pointers.

Space complexity: O(n), where n is the length of the input array. This is because we need to store the squared elements in a separate array.

### Using a priority queue:

We can use a priority queue to keep track of the squared numbers, and then pop them from the queue and add them to the output array in sorted order.

That is, we add the squares of each element in the array to a priority queue, and then remove elements from the priority queue and add them to a result array. This approach has a time complexity of O(n log n) since adding and removing elements from a priority queue takes log(n) time.

#### Algorithm:

1. Initialize a priority queue.
2. Iterate through each number in the input array and add its square to the priority queue.
3. While the priority queue is not empty, pop the smallest element from the priority queue and add it to the output array.
4. Return the output array.
Note that in the last example, we assumed that a PriorityQueue data structure is available in C#. If it's not, then we can implement one ourselves, or use a different data structure like a SortedSet.

Time complexity: O(nlogn), where n is the length of the input array. This is because we need to insert each squared element into the priority queue, which takes O(logn) time for each insertion, and we insert n elements.

Space complexity: O(n), where n is the length of the input array. This is because we need to store the squared elements in a priority queue.

### Using the fact that the array is sorted:

Since the input array is sorted, we can start by finding the index of the first non-negative number in the array, and then use a two-pointer approach to merge the squares of the numbers to the left and right of this index.

We have to find the first non-negative element in the array and use two pointers starting from this index to traverse the array. Compare the squares of the two elements pointed to by the pointers and add the smaller square to a result array from the start. Then move the pointer pointing to the smaller element towards the middle of the array. Repeat this process until both pointers meet.

#### Algorithm:

1. Initialize two pointers, one at this index and one at the index directly to its left.
2. Initialize an empty output array.
3. While the pointer to the left of the non-negative index is greater than or equal to 0, and the pointer to the right of the non-negative index is less than the length of the input array, compare the squares of the numbers at the two pointers.
4. Insert the smaller squared number into the output array and move the corresponding pointer accordingly.
5. Continue until one of the pointers reaches the end of the array.
6. If there are any remaining numbers to be squared in the input array, square them and add them to the output array.
7. Return the output array.

Time complexity: O(n), where n is the length of the input array. This is because we traverse the array once with two pointers.

Space complexity: O(n), where n is the length of the input array. This is because we need to store the squared elements in a separate array.

The most optimal approach is Approach 2: Two-pointer approach. It has a time complexity of O(n), which is the best we can do for this problem, and a space complexity of O(n), which is the same as the other approaches. It doesn't require any extra data structures like a priority queue or a heap and is easy to implement.

There may be other approaches to solving this problem as well, but these are a few common ones.

Share: