# 2022-05-16

## [977. Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)

### Description

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?

### Solution

```go
func sortedSquares(nums []int) []int {
    length := len(nums)
    left, right := 0, length-1
    res := make([]int, length)

    for pos := length - 1; pos >= 0; pos-- {
        if l, r := nums[left]*nums[left], nums[right]*nums[right]; l > r {
            res[pos] = l
            left++
        } else {
            res[pos] = r
            right--
        }
    }
    return res
}
```

## [189. Rotate Array](https://leetcode.com/problems/rotate-array/)

### Description

Given an array, rotate the array to the right by `k` steps, where `k` is non-negative.

**Example 1:**

```
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
```

**Example 2:**

```
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
```

**Constraints:**

* `1 <= nums.length <= 105`
* `-231 <= nums[i] <= 231 - 1`
* `0 <= k <= 105`

**Follow up:**

* Try to come up with as many solutions as you can. There are at least **three** different ways to solve this problem.
* Could you do it in-place with `O(1)` extra space?

### Solution

```go
func rev(nums []int) {
    length := len(nums)
    for i, j := 0, length-1; i < length/2; i++ {
        nums[i], nums[j-i] = nums[j-i], nums[i]
    }
}

func rotate(nums []int, k int) {
    k %= len(nums)
    rev(nums)
    rev(nums[k:])
    rev(nums[:k])
}
```