Problem

Given an array, rotate the array to the right by k steps, where k is non-negative. Follow up: Rotate an array in place.

Examples

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]

Solution

Method 1 - Trivial Solution Using Extra Space

To rotate an array right by k positions, we need to shift the array to the right by k % n, making space on the left for the last k % n elements of the original array. The simple solution involves using a temporary array of size k % n to store the rightmost k % n elements. Then, shift the original array to the right by k % n positions, and finally copy the saved elements from the temporary array to the left side of the original array. The same logic can be applied for left rotation.

Code

Java
class Solution {
	public void rotate(int[] nums, int k) {
		k = k % nums.length; // if k > nums.length
	
		int[] result = new int[nums.length];
	
		for (int i = 0; i<k; i++) {
			result[i] = nums[nums.length - k + i];
		}
	
		int j = 0;
		for (int i = k; i<nums.length; i++) {
			result[i] = nums[j];
			j++;
		}
	
		System.arraycopy(result, 0, nums, 0, nums.length);
	}
}
Python
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k = k % n  # Ensure k is within the bounds of the array size

        # Create a temporary array to store the result
        result = [0] * n

        # Copy the last k elements to the beginning of the result array
        for i in range(k):
            result[i] = nums[n - k + i]

        # Copy the remaining elements to the result array
        for i in range(k, n):
            result[i] = nums[i - k]

        # Copy the result array back into the original array
        for i in range(n):
            nums[i] = result[i]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n), due to the temporary array

Method 2 - In Place Using Bubble Sort

Can we do this in O(1) space? This solution is like a bubble sort.

Here is an example (length=7, k=3):

i=0
0 1 2 3 4 5 6
0 1 2 3 4 6 5
...
6 0 1 2 3 4 5
i=1
6 0 1 2 3 5 4
...
5 6 0 1 2 3 4
i=2
5 6 0 1 2 4 3
...
4 5 6 0 1 2 3

Code

Java
class Solution {
	public void rotate(int[] arr, int k) {
		if (arr == null || k<0) {
			throw new IllegalArgumentException("Illegal argument!");
		}
	
		for (int i = 0; i<k; i++) {
			for (int j = arr.length - 1; j > 0; j--) {
				swap(arr, j, j - 1);
			}
		}
	}
}
Python
class Solution:
    def rotate(self, arr: list[int], k: int) -> None:
        if arr is None or k < 0:
            raise ValueError("Illegal argument!")
        
        n = len(arr)
        k = k % n  # Ensure k is within the bounds of the array size

        for i in range(k):
            for j in range(n - 1, 0, -1):
                self.swap(arr, j, j - 1)
    
    def swap(self, arr: list[int], i: int, j: int) -> None:
        arr[i], arr[j] = arr[j], arr[i]

Complexity

  • ⏰ Time complexity: O(n * k)
  • 🧺 Space complexity: O(1)

Method 3 - Using Reverse Function

Consider rotating an array to the right by k = 2 positions:

arr = [0 1 2 3 4 5 6]
rot = [5 6 0 1 2 3 4]

Here, the last k elements become the start of the array, and the remaining n-k elements follow.

To achieve this, we can reverse the entire array, then reverse the first k elements, and finally reverse the remaining n-k elements:

reverse(A, 0, n - 1);
reverse(array, 0, k - 1);        
reverse(array, k, n - 1);

For example:

arr  = [0 1 2 3 4 5 6]
rev1 = [6 5 4 3 2 1 0]
rev2 = [5 6 4 3 2 1 0]
rev3 = [5 6 0 1 2 3 4]

This method gives the same result.

We can perform this in-place using simple reverse swaps:

A=[1, 2, 3, 4, 5, 6]  and k=2
 ^
 rotation point

1. Reverse unrotated part A[..n-k-1]
A=[4, 3, 2, 1, 5, 6]
 ^

2. Reverse rotated part A[n-k..]
A=[4, 3, 2, 1, 6, 5]
 ^

3. Reverse the whole array
A=[5, 6, 1, 2, 3, 4]

Code

Java
class Solution {
	public void rotate(int[] nums, int k) {
		rotateArrayRight(nums, k);
	}
	void rotateArrayRight(int[] array, int rotatePos) {
		int n = array.length;
		rotatePos = rotatePos % n;
		reverseBetweenRange(array, 0, n - 1);
		reverseBetweenRange(array, 0, rotatePos - 1);
		reverseBetweenRange(array, rotatePos, n - 1);
	}
	
	void reverseBetweenRange(int[] array, int start, int end) {
		while (start < end) {
			swap(array, start++, end--);
		}
	}
	void swap(int[] A, int i, int j) {
		int tmp = A[i];
		A[i] = A[j];
		A[j] = tmp;
	}
}
Python
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        self.rotate_array_right(nums, k)
    
    def rotate_array_right(self, array: List[int], rotate_pos: int) -> None:
        n = len(array)
        rotate_pos = rotate_pos % n  # Ensure rotate_pos is within the bounds of the array size

        self.reverse_between_range(array, 0, n - 1)
        self.reverse_between_range(array, 0, rotate_pos - 1)
        self.reverse_between_range(array, rotate_pos, n - 1)
    
    def reverse_between_range(self, array: List[int], start: int, end: int) -> None:
        while start < end:
            self.swap(array, start, end)
            start += 1
            end -= 1
    
    def swap(self, array: List[int], i: int, j: int) -> None:
        array[i], array[j] = array[j], array[i]

Complexity

  • ⏰ Time complexity: O(n), we can rotate an array using 3 simple O(n) reverse using only in-place swaps.
  • 🧺 Space complexity: O(1)