Rotate Array

---

Rotate Array: 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 <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

---

Try this Problem on your own or check similar problems:

1. Rotate List

Solution:

Java

class Solution {
  public void rotate(int[] nums, int k) {
      int n = nums.length, numberOfRotations = k % n;
      if(numberOfRotations == 0) return;

      reverse(nums, 0, n - 1);
      reverse(nums, 0, numberOfRotations - 1);
      reverse(nums, numberOfRotations, n - 1);
  }

  private void reverse(int[] nums, int start, int end){
    int i =  start, j = end;
    while(i < j){
        swap(nums, i++, j--);
    }
  }

  private void swap(int[] nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

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;
  const numberOfRotations = k % n;
  if (numberOfRotations === 0) return;

  reverse(nums, 0, n - 1);
  reverse(nums, 0, numberOfRotations - 1);
  reverse(nums, numberOfRotations, n - 1);
};

function reverse(nums, start, end) {
  let i = start;
  let j = end;
  while (i < j) {
    swap(nums, i++, j--);
  }
}

function swap(nums, i, j) {
  const temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

Python

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(nums, start, end):
          i = start
          j = end
          while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
        n = len(nums)
        number_of_rotations = k % n
        if number_of_rotations == 0:
            return

        reverse(nums, 0, n - 1)
        reverse(nums, 0, number_of_rotations - 1)
        reverse(nums, number_of_rotations, n - 1)

C++

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        int number_of_rotations = k % n;
        if (number_of_rotations == 0)
            return;

        reverse(nums, 0, n - 1);
        reverse(nums, 0, number_of_rotations - 1);
        reverse(nums, number_of_rotations, n - 1);
    }
    void reverse(vector<int>& nums, int start, int end) {
        int i = start;
        int j = end;
        while (i < j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }

    void swap(int& a, int& b) {
        int temp = a;
        a = b;
        b = temp;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

We traverse the array in linear time and since we do only in-place operations we have constant space complexity. It turns out that we only need 3 reverse operations to get the desired result. We also check if we have k > n and we clamp it numberOfRotations = k % n, since if we rotate the array of length n with k rotations where k==n we will get the same array. The following diagram shows how we use reverse function 3 times to get the desired results: ---->--> for k = 2 we want to get -->----> (where each - presents one element in array):

1. reverse <--<----
2. reverse --><----
3. reverse -->---->, which is also our desired result.