# LeetCode 189: Rotate Array

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

We need to rotate the array to the right by `k` steps.

Rotating right by one step means the last element moves to the front, and every other element shifts one position to the right.

We must modify `nums` in-place.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` and integer `k` |
| Output | Nothing is returned |
| Mutation | Modify `nums` in-place |
| Operation | Rotate right by `k` steps |

Example function shape:

```python
def rotate(nums: list[int], k: int) -> None:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
```

Rotate right once:

```text
[7, 1, 2, 3, 4, 5, 6]
```

Rotate right twice:

```text
[6, 7, 1, 2, 3, 4, 5]
```

Rotate right three times:

```text
[5, 6, 7, 1, 2, 3, 4]
```

So the final array is:

```python
[5, 6, 7, 1, 2, 3, 4]
```

Example 2:

```python
nums = [-1, -100, 3, 99]
k = 2
```

After rotating right by `2` steps:

```python
[3, 99, -1, -100]
```

## First Thought: Move One Step at a Time

A simple idea is to rotate the array one step, then repeat this `k` times.

For one right rotation:

1. Save the last element.
2. Shift every other element one position right.
3. Put the saved last element at index `0`.

This works, but it costs `O(n)` time for each step.

If we repeat it `k` times, the time complexity is:

```text
O(nk)
```

This is too slow when `k` is large.

## Key Insight

A rotation by `k` steps splits the array into two parts.

For:

```python
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
```

The last `k` elements should move to the front:

```text
[5, 6, 7]
```

The earlier elements should move after them:

```text
[1, 2, 3, 4]
```

So the result is:

```text
[5, 6, 7, 1, 2, 3, 4]
```

We can create this in-place using three reversals.

Start:

```text
[1, 2, 3, 4, 5, 6, 7]
```

Reverse the whole array:

```text
[7, 6, 5, 4, 3, 2, 1]
```

Reverse the first `k` elements:

```text
[5, 6, 7, 4, 3, 2, 1]
```

Reverse the remaining elements:

```text
[5, 6, 7, 1, 2, 3, 4]
```

Now the array is rotated correctly.

## Algorithm

1. Let `n = len(nums)`.
2. Reduce `k` using modulo:

```python
k %= n
```

3. Reverse the whole array.
4. Reverse the first `k` elements.
5. Reverse the remaining `n - k` elements.

The modulo step matters because rotating by `n` steps gives the same array.

For example:

```text
k = 10
n = 7
```

Rotating by `10` steps is the same as rotating by:

```text
10 % 7 = 3
```

steps.

## Correctness

Let the original array be split into two parts:

```text
A B
```

where `B` is the last `k` elements and `A` is everything before it.

The target rotated array is:

```text
B A
```

When we reverse the whole array, we get:

```text
reverse(B) reverse(A)
```

Then we reverse the first `k` elements. This changes `reverse(B)` back into `B`.

Now the array is:

```text
B reverse(A)
```

Then we reverse the remaining elements. This changes `reverse(A)` back into `A`.

The final array is:

```text
B A
```

That is exactly the array rotated right by `k` steps.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each element is swapped a constant number of times |
| Space | `O(1)` | Only pointer variables are used |

## Implementation

```python
class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        n = len(nums)
        k %= n

        def reverse(left: int, right: int) -> None:
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)
```

## Code Explanation

This gets the array length:

```python
n = len(nums)
```

This reduces unnecessary full rotations:

```python
k %= n
```

If `k` is larger than `n`, only the remainder matters.

The helper function reverses a section of the array:

```python
def reverse(left: int, right: int) -> None:
```

It swaps the two ends and moves inward:

```python
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
```

Then we apply the three-reversal method:

```python
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
```

The first reversal puts the last `k` elements near the front, but reversed.

The second reversal fixes those `k` elements.

The third reversal fixes the remaining elements.

## Alternative Implementation With Extra Array

This version is simpler, but uses `O(n)` extra space.

```python
class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        n = len(nums)
        k %= n

        rotated = nums[-k:] + nums[:-k]

        for i in range(n):
            nums[i] = rotated[i]
```

For interviews, the in-place reversal version is usually preferred.

## Testing

```python
def run_tests():
    s = Solution()

    nums = [1, 2, 3, 4, 5, 6, 7]
    s.rotate(nums, 3)
    assert nums == [5, 6, 7, 1, 2, 3, 4]

    nums = [-1, -100, 3, 99]
    s.rotate(nums, 2)
    assert nums == [3, 99, -1, -100]

    nums = [1]
    s.rotate(nums, 0)
    assert nums == [1]

    nums = [1, 2]
    s.rotate(nums, 3)
    assert nums == [2, 1]

    nums = [1, 2, 3]
    s.rotate(nums, 3)
    assert nums == [1, 2, 3]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,3,4,5,6,7]`, `k = 3` | Main example |
| `[-1,-100,3,99]`, `k = 2` | Checks negative values |
| Single element | Array remains unchanged |
| `k > n` | Checks modulo reduction |
| `k = n` | Full rotation returns original array |