Problem description:

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

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

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]
``` 

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.


### Solution:

The following solution can solve it in one pass. The idea is to check from two side of the array. Since the array is already sorted, we can check the `absolute value` from two sides, and determine which value is greater.

```python
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        res = [0]*len(nums)
        i, j, k = 0, len(nums)-1, len(nums)-1
        
        while i <= j:
            if abs(nums[i]) < abs(nums[j]):
                res[k] = nums[j]**2
                j -= 1
            else:
                res[k] = nums[i]**2
                i += 1
            k -= 1
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        //start from two side of the array
        int i= 0, j= A.size()-1, k= A.size()-1;
        vector<int> res(A.size());
        
        while(i<= j){
            
            if(abs(A[i])> abs(A[j])){
                res[k]= A[i]*A[i];
                i++;
            }
            else{
                res[k]= A[j]*A[j];
                j--;
            }
            k--;
        }
        return res;
    }
};

time complexity: $O(n)$
space complexity: $O(n)$
reference: