189. Rotate Array

LeetCode Problem Link (opens new window)

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

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?

Example 1:

• Input: nums = [1,2,3,4,5,6,7], k = 3
• Output: [5,6,7,1,2,3,4]
• Explanation: Rotate 1 step 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 step to the right: [99,-1,-100,3]. Rotate 2 steps to the right: [3,99,-1,-100].

Thought Process

This problem is quite common in string manipulation. Here are some related string reversal problems:

• String: 0541.Reverse String II (opens new window)
• String: 0151.Reverse Words in a String (opens new window)
• String: SwordOffer58-II.Left Rotation of String (opens new window)

This problem is very similar to String: SwordOffer58-II.Left Rotation of String (opens new window). In that problem, the string is left-rotated, whereas this problem is about right-rotation.

Note that the problem requires an in-place algorithm with O(1) extra space.

Here, I provide a method to achieve this rotation.

In String: SwordOffer58-II.Left Rotation of String (opens new window), we mentioned that the following steps can left-rotate a string:

1. Reverse the first n substring
2. Reverse the substring from n to the end
3. Reverse the entire string

This problem rotates to the right, so the order of reversing steps needs to be adjusted. Prioritize reversing the entire string first, as follows:

1. Reverse the entire string
2. Reverse the first k substring
3. Reverse the substring from k to the end

It's important to note that this problem has a small trick: what should we do if k is greater than nums.size()?

A simple way to think about this is:

For example, [1,2,3,4,5,6,7] rotated to the right 15 times results in [7,1,2,3,4,5,6].

So, in fact, it's equivalent to right-rotating k % nums.size() times, i.e., 15 % 7 = 1.

Here is the C++ code:

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

Other Language Versions

Java

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

Python

Method 1: Local Reversal + Overall Reversal

class Solution:
    def rotate(self, A: List[int], k: int) -> None:
        def reverse(i, j):
            while i < j:
                A[i], A[j] = A[j], A[i]
                i += 1
                j -= 1
        n = len(A)
        k %= n
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

Method 2: Using Modulo

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        copy = nums[:]
        for i in range(len(nums)):
            nums[(i + k) % len(nums)] = copy[i]
        return nums
        # Note: This method increases the space complexity to O(n) because we need to create a copy array.
        # But it's still a valuable approach to consider.

Go

func rotate(nums []int, k int)  {
    l := len(nums)
    index := l - k%l
    reverse(nums)
    reverse(nums[:l-index])
    reverse(nums[l-index:])
}
func reverse(nums []int){
    l := len(nums)
    for i := 0; i < l/2; i++ {
        nums[i], nums[l-1-i] = nums[l-1-i], nums[i]
    }
}

JavaScript

var rotate = function (nums, k) {
  function reverse(nums, i, j) {
    while (i < j) {
      [nums[i],nums[j]] = [nums[j],nums[i]]; // Destructuring assignment
      i++;
      j--;
    }
  }
  let n = nums.length;
  k %= n;
  if (k) {
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
  }
};

TypeScript

function rotate(nums: number[], k: number): void {
    const length: number = nums.length;
    k %= length;
    reverseByRange(nums, 0, length - 1);
    reverseByRange(nums, 0, k - 1);
    reverseByRange(nums, k, length - 1);
};
function reverseByRange(nums: number[], left: number, right: number): void {
    while (left < right) {
        const temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    }
}

Rust

impl Solution {
    pub fn rotate(nums: &mut Vec<i32>, k: i32) {
        let k = k as usize % nums.len();
        nums.reverse();
        nums[..k].reverse();
        nums[k..].reverse();
    }
}