Data structures and algorithms
## Squares of a Sorted Array

###### Example 1:

###### Example 2:

###### Constraints:

##### Solution:

###### Time/Space Complexity:

###### Explanation:

comments powered by Disqus

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

```
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]
```

`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:

```
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 Complexity:
*O(n)* - Space Complexity:
*O(1)*

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

Don’t settle for anything less than the crown. Join our newsletter and become the King of Interviews! **Click here** to join now and get the latest updates.