> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/array/rotate-array.md).

# Rotate Array

{% hint style="info" %}
Array, Two Pointers
{% endhint %}

Given an integer array `nums`, 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]
```

### Solutions

The problem is asking to rotate an array to the right by `k` steps. This means that each element in the array should be moved `k` positions to the right, and the elements that go beyond the end of the array should be moved to the start of the array.

#### **Approach – Brute Force Technique**

In the brute force approach, we rotate the array `k` times. In each rotation, we move each element to its next position and move the last element to the start of the array.

**Steps**

1. **Define the function:** The function `Rotate` is defined with two parameters, `nums` (an array of integers) and `k` (the number of steps to rotate).
2. **Outer loop:** The outer loop runs `k` times. Each iteration of this loop corresponds to a single step of rotation.
3. **Store the last element:** Before shifting the elements, the last element of the array is stored in the variable `temp`. This is because it will be overwritten during the shifting process and we need to place it at the start of the array.
4. **Shift elements to the right:** The inner loop runs from the end of the array to the start, shifting each element one position to the right. This is done by setting `nums[j]` to `nums[j - 1]`.
5. **Place the last element at the start:** After all elements have been shifted, there is an empty spot at the start of the array (i.e., `nums[0]`). The last element that we stored in `temp` is placed here.
6. **Repeat:** The process is repeated `k` times to achieve the required rotation.

```csharp
public class Solution
{
    public void Rotate(int[] nums, int k)
    {
        for (int i = 1; i <= k; i++)
        {
            int temp = nums[nums.Length - 1];
            for (int j = nums.Length - 1; j > 0; j--)
            {
                nums[j] = nums[j - 1];
            }
            if (nums.Length > 0)
            {
                nums[0] = temp;
            }
        }
    }
}

```

> Complexity

* **Time Complexity:** O(n\*k)
* **Auxiliary Space:** O(1)

#### **Approach – Two Pointers Technique**

In the optimized approach, we use the reverse operation to achieve the rotation. We first reverse the entire array, then reverse the first `k` elements, and finally reverse the remaining `n - k` elements.

**Steps**

1. **Calculate the effective number of rotations:** The number of rotations `k` is taken modulo the length of the array `n`. This is because rotating the array `n` times doesn't change the array, so we only need to consider the remainder of `k` divided by `n`.
2. **Reverse the entire array:** The `Reverse` function is called with parameters `0` and `n - 1`, which reverses the entire array.
3. **Reverse the first part of the array:** The `Reverse` function is called again with parameters `0` and `k - 1`, which reverses the first `k` elements of the array.
4. **Reverse the second part of the array:** The `Reverse` function is called one more time with parameters `k` and `n - 1`, which reverses the remaining `n - k` elements of the array.

The `Reverse` function is a helper function that reverses the elements in the `nums` array between the `start` and `end` indices. It does this by swapping the elements at the `start` and `end` indices, and then incrementing `start` and decrementing `end` until `start` is no longer less than `end`.

```csharp
public class Solution
{
    public void Rotate(int[] nums, int k)
    {
        int n = nums.Length;
        k = k % n;
        Reverse(nums, 0, n - 1);
        Reverse(nums, 0, k - 1);
        Reverse(nums, k, n - 1);
    }

    public void Reverse(int[] nums, int start, int end)
    {
        while (start < end)
        {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

}

```

> Complexity

* **Time Complexity:** O(n)
* **Auxiliary Space:** O(1)