> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/rotate-array.md).

# 189. Rotate Array

### Description

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

**Follow up:**

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

### Constraints

* `1 <= nums.length <= 2 * 10^4`
* It's guaranteed that `nums[i]` fits in a 32 bit-signed integer.
* `k >= 0`

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/rotate-array/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="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]
{% endtab %}

{% tab title="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]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(n×k). All the numbers are shifted by one step(O(n)) 
 *    k times(O(n)).
 * Space complexity : O(1). No extra space is used.
 */

class Solution {
  public void rotate(int[] nums, int k) {
    // speed up the rotation
    k %= nums.length;
    int temp, previous;
    for (int i = 0; i < k; i++) {
      previous = nums[nums.length - 1];
      for (int j = 0; j < nums.length; j++) {
        temp = nums[j];
        nums[j] = previous;
        previous = temp;
      }
    }
  }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(n). One pass is used to put the numbers in the new array. 
 *    And another pass to copy the new array to the original one.
 * Space complexity : O(n). Another array of the same size is used.
 */
 
 class Solution {
  public void rotate(int[] nums, int k) {
    int[] a = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
      a[(i + k) % nums.length] = nums[i];
    }
    for (int i = 0; i < nums.length; i++) {
      nums[i] = a[i];
    }
  }
}
```

{% endtab %}

{% tab title="Solution 3" %}

```java
/**
 * Time complexity : O(n). Only one pass is used.
 * Space complexity : O(1). Constant extra space is used.
 */
 
 class Solution {
  public void rotate(int[] nums, int k) {
    k = k % nums.length;
    int count = 0;
    for (int start = 0; count < nums.length; start++) {
      int current = start;
      int prev = nums[start];
      do {
        int next = (current + k) % nums.length;
        int temp = nums[next];
        nums[next] = prev;
        prev = temp;
        current = next;
        count++;
      } while (start != current);
    }
  }
}
```

{% endtab %}

{% tab title="Solution 4" %}

```java
/**
 * Time complexity : O(n). n elements are reversed a total of three times.
 * Space complexity : O(1). No extra space is used.
 */
 
 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);
    }
    
    private void reverse(int[] nums, int left, int right) {
        while(left < right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*