# Rotate Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rotate-array)
Canonical: https://scaleengineer.com/dsa/problems/rotate-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [American Express](https://scaleengineer.com/companies/american-express), [Capgemini](https://scaleengineer.com/companies/capgemini), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Oracle](https://scaleengineer.com/companies/oracle), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [Netflix](https://scaleengineer.com/companies/netflix), [razorpay](https://scaleengineer.com/companies/razorpay), [DXC Technology](https://scaleengineer.com/companies/dxc-technology), [Scale AI](https://scaleengineer.com/companies/scale-ai)
---
## Problem
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]

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

# Approaches
## Brute Force: Rotate One by One
This approach simulates the rotation process step by step. For each of the `k` rotation steps, it moves every element in the array one position to the right. The last element is moved to the first position.
**Time:** O(n * k) · **Space:** O(1)
**Pros:** Simple to understand and implement.; It's an in-place solution, using constant extra space.
**Cons:** Extremely inefficient for large arrays or large values of `k`.; Will likely result in a 'Time Limit Exceeded' (TLE) error on most coding platforms for larger constraints.
### Explanation
The most straightforward way to solve the problem is to literally rotate the array `k` times. A single right rotation involves taking the last element and moving it to the front, while shifting every other element one position to the right.

We can implement this by running a loop `k` times. Inside this loop, we perform the single rotation. To avoid unnecessary rotations when `k` is larger than the array length `n`, we first take `k = k % n`.

```java
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        // To handle cases where k > n
        k %= n;
        
        for (int i = 0; i < k; i++) {
            int lastElement = nums[n - 1];
            // Shift all elements one position to the right
            for (int j = n - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            // Place the last element at the front
            nums[0] = lastElement;
        }
    }
}
```
### Algorithm
- 1. Calculate the effective rotation count by taking `k = k % nums.length`.
- 2. Repeat the rotation process `k` times.
- 3. In each of the `k` iterations, perform a single right rotation:
  - a. Store the last element of the array in a temporary variable, `last = nums[n-1]`.
  - b. Shift all elements from index `n-2` down to `0` one position to the right. This can be done by iterating from `j = n-1` down to `1` and setting `nums[j] = nums[j-1]`.
  - c. Place the stored `last` element at the beginning of the array: `nums[0] = last`.

## Using an Extra Array
This approach uses an auxiliary array to store the rotated elements. Each element `nums[i]` is placed at its new position `(i + k) % n` in the new array. Finally, the new array is copied back to the original array.
**Time:** O(n) · **Space:** O(n)
**Pros:** Time complexity is linear, which is a significant improvement over the brute-force method.; The logic is straightforward and easy to implement correctly.
**Cons:** Requires extra space proportional to the size of the input array.; Fails the follow-up requirement of solving it in-place with O(1) extra space.
### Explanation
A more efficient approach in terms of time complexity is to use an extra array. We can determine the final position of each element and place it there directly in a new array. An element currently at index `i` will be at index `(i + k) % n` after the rotation, where `n` is the length of the array.

We can create a new array of the same size, iterate through the original array, and place each element in its correct final position in the new array. Once the new array is fully populated, we copy it back to the original array.

```java
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n];
        
        for (int i = 0; i < n; i++) {
            result[(i + k) % n] = nums[i];
        }
        
        // Copy the result back to the original array
        System.arraycopy(result, 0, nums, 0, n);
    }
}
```
### Algorithm
- 1. Create a new array `result` of the same size as `nums`.
- 2. Iterate through the original `nums` array from index `i = 0` to `n-1`.
- 3. For each element `nums[i]`, calculate its new position in the rotated array, which is `(i + k) % n`.
- 4. Place the element `nums[i]` into the `result` array at the calculated new position: `result[(i + k) % n] = nums[i]`.
- 5. After iterating through all elements, copy the contents of the `result` array back into the original `nums` array.

## Cyclic Replacements
This is an in-place approach that moves elements to their correct positions in cycles. It iterates through the array, and for each element, it follows the cycle of replacements until every element is in its final place. The number of cycles is determined by the greatest common divisor (GCD) of the array length `n` and the rotation amount `k`.
**Time:** O(n) · **Space:** O(1)
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1) as it's an in-place algorithm.
**Cons:** The implementation is more complex and less intuitive than other optimal solutions.; The memory access pattern is non-sequential (jumping by `k` steps), which can be less cache-friendly than sequential access.
### Explanation
This is an advanced in-place algorithm that achieves optimal time and space complexity. The core idea is that the rotation permutes elements in disjoint cycles. An element at index `i` moves to `(i+k)%n`, the element there moves to `(i+2k)%n`, and so on, until we return to `i`.

We can process one cycle at a time. We start at an index, say `0`, and move the element to a temporary variable. Then we move the element from its destination to index `0`. We continue this process until the cycle is complete. If `n` and `k` are not coprime, there will be multiple cycles. The number of cycles is `gcd(n, k)`. We need to start a new process for each cycle.

```java
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        if (k == 0) {
            return;
        }
        
        int count = 0; // Number of elements placed
        for (int start = 0; count < n; start++) {
            int current = start;
            int prevValue = nums[start];
            
            do {
                int nextIdx = (current + k) % n;
                int temp = nums[nextIdx];
                nums[nextIdx] = prevValue;
                prevValue = temp;
                current = nextIdx;
                count++;
            } while (start != current);
        }
    }
}
```
### Algorithm
- 1. Reduce `k` by taking `k = k % n`. If `k` is 0, no rotation is needed.
- 2. Initialize a counter `count` for the number of elements placed in their correct positions to 0.
- 3. Loop with a `start` index from `0` to `n-1`. This loop will effectively run `gcd(n, k)` times because the inner loop places multiple elements.
- 4. For each `start`, begin a cycle. Let `current = start` and store the value `nums[start]` in a temporary variable `prev`.
- 5. Use a `do-while` loop to traverse the cycle:
  - a. Calculate the `next` index: `next = (current + k) % n`.
  - b. Swap the value at `nums[next]` with `prev`. `int temp = nums[next]; nums[next] = prev; prev = temp;`
  - c. Move to the next position in the cycle: `current = next`.
  - d. Increment the `count` of placed elements.
- 6. The `do-while` loop terminates when the cycle is complete (i.e., `current == start`).
- 7. The outer loop continues until all elements are placed (`count == n`).

## Using Reversal
This is an elegant and efficient in-place solution. The algorithm consists of three steps: first, reverse the entire array. Second, reverse the first `k` elements. Third, reverse the remaining `n-k` elements. This sequence of reversals correctly places all elements in their rotated positions.
**Time:** O(n) · **Space:** O(1)
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1) as it's an in-place algorithm.; The code is clean, concise, and generally easier to implement correctly than the cyclic replacement method.; Memory access is sequential during reversals, which is cache-friendly.
**Cons:** The underlying logic might not be immediately obvious without working through an example.
### Explanation
This is a very clever in-place solution with O(n) time complexity. The idea is that a right rotation by `k` moves the last `k` elements to the front and the first `n-k` elements to the back.

Let's take `nums = [1,2,3,4,5,6,7]` and `k = 3`. The goal is `[5,6,7,1,2,3,4]`.

1.  **Reverse the entire array:** The original array `[1,2,3,4,5,6,7]` becomes `[7,6,5,4,3,2,1]`.
2.  **Reverse the first `k` elements:** The first `k=3` elements are `[7,6,5]`. Reversing them gives `[5,6,7]`. The array is now `[5,6,7,4,3,2,1]`.
3.  **Reverse the remaining `n-k` elements:** The rest of the elements are `[4,3,2,1]`. Reversing them gives `[1,2,3,4]`. The array is now `[5,6,7,1,2,3,4]`, which is the correct result.

This three-step reversal process works for any `n` and `k`.

```java
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        
        // Step 1: Reverse the entire array
        reverse(nums, 0, n - 1);
        // Step 2: Reverse the first k elements
        reverse(nums, 0, k - 1);
        // Step 3: Reverse the remaining n-k elements
        reverse(nums, k, n - 1);
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}
```
### Algorithm
- 1. Define a helper function `reverse(nums, start, end)` that reverses the sub-array of `nums` from the `start` index to the `end` index.
- 2. In the main `rotate` function, first handle the case where `k` is larger than the array length by taking `k = k % nums.length`.
- 3. Reverse the entire array. Call `reverse(nums, 0, n - 1)`.
- 4. Reverse the first `k` elements of the now-reversed array. Call `reverse(nums, 0, k - 1)`.
- 5. Reverse the remaining `n-k` elements. Call `reverse(nums, k, n - 1)`.

# Solutions
### CSharp

```csharp
public class Solution {
    private int[] nums;
    public void Rotate(int[] nums, int k) {
        this.nums = nums;
        int n = nums.Length;
        k %= n;
        reverse(0, n - 1);
        reverse(0, k - 1);
        reverse(k, n - 1);
    }
    private void reverse(int i, int j) {
        for (; i < j; ++i, --j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
}
```

### Java

```java
class Solution { private int [] nums ; public void rotate ( int [] nums , int k ) { this . nums = nums ; int n = nums . length ; k %= n ; reverse ( 0 , n - 1 ); reverse ( 0 , k - 1 ); reverse ( k , n - 1 ); } private void reverse ( int i , int j ) { for (; i < j ; ++ i , -- j ) { int t = nums [ i ]; nums [ i ] = nums [ j ]; nums [ j ] = t ; } } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} k * @return {void} Do not return anything, modify nums in-place instead. */ var rotate =
  function (nums, k) {
    const n = nums.length;
    k %= n;
    const reverse = (i, j) => {
      for (; i < j; ++i, --j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
      }
    };
    reverse(0, n - 1);
    reverse(0, k - 1);
    reverse(k, n - 1);
  };

```

### CPP

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

### Python

```python
class Solution : def rotate ( self , nums : List [ int ], k : int ) -> None : k %= len ( nums ) nums [:] = nums [ - k :] + nums [: - k ] ############ class Solution : def rotate ( self , nums : List [ int ], k : int ) -> None : """ Do not return anything, modify nums in-place instead. """ n = len ( nums ) k %= n if n < 2 or k == 0 : return nums [:] = nums [:: - 1 ] nums [: k ] = nums [: k ][:: - 1 ] nums [ k :] = nums [ k :][:: - 1 ] ############ class Solution ( object ): def rotate ( self , nums , k ): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ if len ( nums ) == 0 or k == 0 : return def reverse ( start , end , s ): while start < end : s [ start ], s [ end ] = s [ end ], s [ start ] start += 1 end -= 1 n = len ( nums ) - 1 k = k % len ( nums ) reverse ( 0 , n - k , nums ) reverse ( n - k + 1 , n , nums ) reverse ( 0 , n , nums )
```