# Leetcode: Squares of a Sorted Array

Squares of a Sorted Array

Similar Problems:

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:

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

Example 2:

```Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]
```

Note:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Two pointers
```// Blog link: https://code.dennyzhang.com/squares-of-a-sorted-array
// Basic Idea: Two pointers
// Complexity: Time O(n), Space O(1)
func sortedSquares(A []int) []int {
res := make([]int, len(A))
i, j := 0, len(A)-1
for k:=len(A)-1; k>=0; k-- {
v1, v2 := A[i]*A[i], A[j]*A[j]
if v1>=v2 {
res[k] = v1
i++
} else {
res[k] = v2
j--
}
}
return res
}
```

• Merge sort
```// Blog link: https://code.dennyzhang.com/squares-of-a-sorted-array
// Basic Idea: merge sort
// Complexity: Time O(n), Space O(n)
func sortedSquares(A []int) []int {
B1, B2 := []int{}, []int{}
for _, v := range A {
if v < 0 {
B1 = append(B1, v*v)
} else {
B2 = append(B2, v*v)
}
}
// Merge B1 and B2
i, j := len(B1)-1, 0
res := []int{}
for i>=0 && j<len(B2) {
if B1[i] <= B2[j] {
res = append(res, B1[i])
i--
} else {
res = append(res, B2[j])
j++
}
}
for i>=0 {
res = append(res, B1[i])
i--
}
for j<len(B2) {
res = append(res, B2[j])
j++
}
return res
}
```

Share It, If You Like It.