# LeetCode Solution, Easy, 977. Squares of a Sorted Array

# [977. Squares of a Sorted Array](https://leetcode.com/problems/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_.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

- `1 <= nums.length <= 10**4`
- `-10**4 <= nums[i] <= 10**4`
- `nums` is sorted in **non-decreasing** order.

**Follow up:** Squaring each element and sorting the new array is very trivial, could you find an `O(n)` solution using a different approach?

### 題目翻譯

今天已經有一個升序排列的陣列 `nums`，然後需要將其中的元素都變成平方值之後再依照平方後的大小排列。其中可以的話，想辦法達到時間複雜度 `O(n)`

## 解法解析

今天在不考慮時間複雜度的條件下，我們可以很單純的使用一些內建的函數來快速的達到這個需求。但是如果要達到時間複雜度的限制的話，就會需要使用到 Two Pointers 來做解答。因為這個陣列本身就已經排序過了，考量有負值的情況下，平方後大小的排序其實就會是從兩側往內部縮小。所以使用 Two pointers 剛好符合使用情境。

### 解法範例

#### Go

##### Built-In

```go
func sortedSquares(nums []int) []int {
	for i, val := range nums {
		nums[i] = val * val
	}
	sort.Ints(nums)
	return nums
}
```

##### Two Pointers

```go
func sortedSquares(nums []int) []int {
	var n, lastIndex, left, right int = len(nums), len(nums) - 1, 0, len(nums) - 1
	result := make([]int, n)

	for left <= right {
		var leftSquare, rightSquare int = nums[left] * nums[left], nums[right] * nums[right]

		if leftSquare < rightSquare {
			result[lastIndex] = rightSquare
			right--
		} else {
			result[lastIndex] = leftSquare
			left++
		}
		lastIndex--
	}
	return result
}
```

#### JavaScript

##### Built-In

```javascript
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
    return nums.map((num) => num * num).sort((a, b) => a - b);
};
```

##### Two Pointers

```javascript
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
    const n = nums.length,
        result = new Array(n).fill(0);
    let lastIndex = n - 1;

    for (let left = 0, right = n - 1; left <= right; ) {
        const leftSquare = nums[left] ** 2;
        const rightSquare = nums[right] ** 2;
        if (leftSquare < rightSquare) {
            result[lastIndex--] = rightSquare;
            right--;
        } else {
            result[lastIndex--] = leftSquare;
            left++;
        }
    }
    return result;
};
```

#### Kotlin

##### Built-In

```kotlin
class Solution {
    fun sortedSquares(nums: IntArray): IntArray {
        return nums.map { it * it }.sorted().toIntArray()
    }
}
```

##### Two Pointers

```kotlin
class Solution {
    fun sortedSquares(nums: IntArray): IntArray {
        val n = nums.size
        val result = IntArray(n)
        var left = 0
        var right = n - 1
        var idx = n - 1

        while (left <= right) {
            val leftSquare = nums[left] * nums[left]
            val rightSquare = nums[right] * nums[right]

            if (leftSquare <= rightSquare) {
                result[idx] = rightSquare
                right--
            } else {
                result[idx] = leftSquare
                left++
            }
            idx--
        }

        return result
    }
}
```

#### PHP

##### Built-In

```php
class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function sortedSquares($nums)
    {
        $ans = array_map(function ($num) {
            return $num * $num;
        }, $nums);
        sort($ans);
        return $ans;
    }
}
```

##### Two Pointers

```php
class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function sortedSquares($nums)
    {
        $n = count($nums);
        $result = array_fill(0, $n, 0);
        $left = 0;
        $right = $n - 1;
        $lastIndex = $n - 1;
        while ($left <= $right) {
            $leftSquare = $nums[$left] ** 2;
            $rightSquare = $nums[$right] ** 2;
            if ($leftSquare < $rightSquare) {
                $result[$lastIndex] = $rightSquare;
                $right--;
            } else {
                $result[$lastIndex] = $leftSquare;
                $left++;
            }
            $lastIndex--;
        }
        return $result;
    }
}
```

#### Python

##### Built-In

```python
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(num * num for num in nums)
```

##### Two Pointers

```python
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        left = 0
        right = n - 1
        for i in range(n - 1, -1, -1):
            if abs(nums[left]) < abs(nums[right]):
                square = nums[right]
                right -= 1
            else:
                square = nums[left]
                left += 1
            result[i] = square ** 2
        return result
```

#### Rust

##### Built-In

```rust
impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let mut res: Vec<i32> = nums.iter().map(|&x| x * x).collect();
        res.sort();
        res
    }
}
```

##### Two Pointers

```rust
impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let mut result = vec![0; nums.len()];
        let mut left = 0;
        let mut right = nums.len() as i32 - 1;
        for i in (0..nums.len()).rev() {
            let mut square = 0;
            let left_square = nums[left as usize] * nums[left as usize];
            let right_square = nums[right as usize] * nums[right as usize];
            if left_square > right_square {
                result[i] = left_square;
                left += 1;
            } else {
                result[i] = right_square;
                right -= 1;
            }
        }

        result
    }
}
```

#### Swift

##### Built-In

```swift
class Solution {
    func sortedSquares(_ nums: [Int]) -> [Int] {
        return nums.map { $0 * $0 }.sorted()
    }
}
```

##### Two Pointers

```swift
class Solution {
    func sortedSquares(_ nums: [Int]) -> [Int] {
        let n = nums.count
        var left = 0
        var right = n - 1
        var result = Array(repeating: 0, count: n)

        for i in (0..<n).reversed() {
            var square = 0
            if abs(nums[left]) > abs(nums[right]) {
                square = nums[left]
                left += 1
            } else {
                square = nums[right]
                right -= 1
            }
            result[i] = square * square
        }

        return result
    }
}
```