# Rotate Array

## Description

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

**Example 1:**

```
Input: [1,2,3,4,5,6,7] and 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: [-1,-100,3,99] and 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]
```

**Note:**

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

## Solutions

### My solution (also optimal)

Idea: directly put numbers in their new positions.

```cpp
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 0 || k % n == 0) return;
        k %= n;
        int count = 0; // number of elements in correct position
        int start = 0;
        while(count < n){
            int i = start;
            int prev = nums[i]; // value of number in previous index
            do{
                i = (i + k) % n; // destination index
                swap(prev, nums[i]);
                ++count;
            }while(i != start);
            ++start;
        }
    }
};
```

### Easier to understand solution

Idea: the objective is to move the first `n - k` numbers to the last `n - k` positions, and move the last `k` numbers to the first `k` positions. If we reverse `nums`, then the original first `n - k` numbers and the last `k` numbers are in correct ranges. Then we reverse the two ranges to make all numbers in correct positions.

**E.g.**,

Original array: `[1, 2, 3, 4, 5, 6]` , k = 4

Objective: `[3, 4, 5, 6, 1, 2]`

After first reversing: `[6, 5, 4, 3, 2, 1]`.`[6, 5, 4, 3]` and `[2, 1]` are in correct ranges but in reversed order.

```cpp
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 0 || k % n == 0) return;
        k %= n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://twchen.gitbook.io/leetcode/array/rotate-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.