notes/OJ notes/pages/Leetcode Rotate-Array.md

# Leetcode Rotate-Array

#### 2022-07-10 08:54

> ##### Algorithms:
>
> #algorithm #array_in_place_operation #reverse_array
>
> ##### Data structures:
>
> #DS #array
>
> ##### Difficulty:
>
> #coding_problem #difficulty_medium
>
> ##### Additional tags:
>
> #leetcode #CS_list_need_practicing #CS_list_need_understanding
>
> ##### Revisions:
>
> N/A

##### Related topics:

##### Links:

- [Link to problem](https://leetcode.com/problems/rotate-array/)

---

### Problem

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

#### Examples

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

### Thoughts

#### Method 1: Array In-place operation

This one is hard.
==#TODO: Revisit this one some other day==

- Reversing a subarray doesn't change the continuity, the neighbors inside the subarray is same.
- Reversing a subarray changes the edge's neighbors

Suppose a array looks like:

```
[1, 2,| 3, 4, 5]
```

If reverse all two subarrays, the neighbors isn't changed
only the orders are changed

```
[1, 2,| 3, 4, 5]:    5-1-2, 1-2-3, 2-3-4, 4-5-1
[2, 1,| 5, 4, 3]:    3-2-1, 2-1-5, 5-1-4, 4-3-2
```

When reversed back, the order is changed back to original, but the two sub-arrays are swapped

```
[3, 4, 5,| 1, 2]
```

By doing this, the order in inner-array isn't changed, but the order of all is changed.

#### Method 2: Copy

Watch out for integer overflow.

#### Method 3: CPP's STL sway subarrays

Remember to sanitize k, when k > size

### Solution

Method 1:

```cpp
class Solution {
  void swap(vector<int> &nums, int l, int r) {
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
  }
  void reverse(vector<int> &nums, int l, int r) {
    while (l < r) {
      swap(nums, l, r);
      l++;
      r--;
    }
  }

public:
  void rotate(vector<int> &nums, int k) {
    const int size = nums.size();
    k = k % size;
    // Reversion
    reverse(nums, 0, size - k - 1);
    reverse(nums, size - k, size - 1);
    reverse(nums, 0, size - 1);
  }
};
```

Method 2:

```cpp
class Solution {
  void swap(vector<int> &nums, int l, int r) {
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
  }

public:
  void rotate(vector<int> &nums, int k) {
    int size = nums.size();
    if (size <= 1) {
      return;
    }
    // Copy
    k = size - k;
    while (k < 0) {
      k += size;
    }
    vector<int> ans(nums.size());
    for (int i = 0; i < size; i++) {
      ans[i] = nums[(i + k) % size];
    }
    for (int i = 0; i < size; i++) {
      nums[i] = ans[i];
    }
  }
};
```

Method 3:

```cpp
class Solution {
  void swap(vector<int> &nums, int l, int r) {
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
  }

public:
  void rotate(vector<int> &nums, int k) {
    int size = nums.size();
    if (size <= 1) {
      return;
    }
    // STL
    k = k % size;
    k = size - k;
    while (k < 0) {
      k += size;
    }

    nums.insert(nums.end(), nums.begin(), nums.begin() + k);
    nums.erase(nums.begin(), nums.begin() + k);
  }
};
```