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:

1
2
3
4
5
6

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:

1
2
3
4
5

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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);
			}
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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:

1
2

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:

1
2
3

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

For example:

1
2
3
4

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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)