Right rotate an array `k` times
In this post, we will see how to right-rotate an array by specified positions. For example, right rotating array { 1, 2, 3, 4, 5, 6, 7 } three times will result in array { 5, 6, 7, 1, 2, 3, 4 }.
1. Rotating k times
The idea is to right-rotate all array elements by one position k times, where k is the given rotation count. This approach is demonstrated below in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <stdio.h> // Function to right-rotate an array by one position void rightRotateByOne(int A[], int n) { int last = A[n - 1]; for (int i = n - 2; i >= 0; i--) { A[i + 1] = A[i]; } A[0] = last; } // Function to right-rotate an array by `k` positions void rightRotate(int A[], int k, int n) { // base case: invalid input if (k < 0 || k >= n) { return; } for (int i = 0; i < k; i++) { rightRotateByOne(A, n); } } int main(void) { int A[] = { 1, 2, 3, 4, 5, 6, 7 }; int k = 3; int n = sizeof(A)/sizeof(A[0]); rightRotate(A, k, n); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; } |
Output:
5, 6, 7, 1, 2, 3, 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import java.util.Arrays; class Main { // Function to right-rotate an array by one position public static void rightRotateByOne(int[] A) { int last = A[A.length - 1]; for (int i = A.length - 2; i >= 0; i--) { A[i + 1] = A[i]; } A[0] = last; } // Function to right-rotate an array by `k` positions public static void rightRotate(int[] A, int k) { // base case: invalid input if (k < 0 || k >= A.length) { return; } for (int i = 0; i < k; i++) { rightRotateByOne(A); } } public static void main(String[] args) { int[] A = { 1, 2, 3, 4, 5, 6, 7 }; int k = 3; rightRotate(A, k); System.out.println(Arrays.toString(A)); } } |
Output:
[5, 6, 7, 1, 2, 3, 4]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
# Function to right-rotate a list by one position def rightRotateByOne(A): last = A[-1] for i in reversed(range(len(A) - 1)): A[i + 1] = A[i] A[0] = last # Function to right-rotate a list by `k` positions def rightRotate(A, k): # base case: invalid input if k < 0 or k >= len(A): return for i in range(k): rightRotateByOne(A) if __name__ == '__main__': A = [1, 2, 3, 4, 5, 6, 7] k = 3 rightRotate(A, k) print(A) |
Output:
[5, 6, 7, 1, 2, 3, 4]
The time complexity of the above solution is O(n.k), where n is the size of the input and k is the rotation count.
2. Using Auxiliary Array
We can reduce the time complexity of the above solution to linear using some extra space. The idea is to store the last k elements of the input array in an auxiliary array of size k. Then shift the first n-k elements of the input array at the end. Finally, put elements of the auxiliary array at their correct positions in the input array.
Following is the implementation in C, Java, and Python based on the above idea:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <stdio.h> // Function to right-rotate an array by `k` positions void rightRotate(int A[], int k, int n) { // base case: invalid input if (k < 0 || k >= n) { return; } // construct an auxiliary array of size `k` and // fill it with the last `k` elements of the input array int aux[k]; for (int i = 0; i < k; i++) { aux[i] = A[n-k+i]; } // shift the first `n-k` elements of the input array at the end for (int i = n-k-1; i >= 0; i--) { A[i+k] = A[i]; } // put the elements of the auxiliary array at their // correct positions in the input array for (int i = 0; i < k; i++) { A[i] = aux[i]; } } int main(void) { int A[] = { 1, 2, 3, 4, 5, 6, 7 }; int k = 3; int n = sizeof(A)/sizeof(A[0]); rightRotate(A, k, n); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; } |
Output:
5, 6, 7, 1, 2, 3, 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
import java.util.Arrays; class Main { // Function to right-rotate an array by `k` positions public static void rightRotate(int[] A, int k) { int n = A.length; // base case: invalid input if (k < 0 || k >= n) { return; } // construct an auxiliary array of size `k` and // fill it with the last `k` elements of the input array int[] aux = new int[k]; for (int i = 0; i < k; i++) { aux[i] = A[n - k + i]; } // shift the first `n-k` elements of the input array at the end for (int i = n - k - 1; i >= 0; i--) { A[i + k] = A[i]; } // put the elements of the auxiliary array at their // correct positions in the input array for (int i = 0; i < k; i++) { A[i] = aux[i]; } } public static void main(String[] args) { int[] A = { 1, 2, 3, 4, 5, 6, 7 }; int k = 3; rightRotate(A, k); System.out.println(Arrays.toString(A)); } } |
Output:
[5, 6, 7, 1, 2, 3, 4]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
# Function to right-rotate a list by `k` positions def rightRotate(A, k): n = len(A) # base case: invalid input if k < 0 or k >= n: return # construct an auxiliary space of size `k` and # fill it with the last `k` elements of the input list aux = [A[n - k + i] for i in range(k)] # shift the first `n-k` elements of the input list at the end for i in reversed(range(n - k)): A[i + k] = A[i] # put the elements of the auxiliary space at their # correct positions in the input list for i in range(k): A[i] = aux[i] if __name__ == '__main__': A = [1, 2, 3, 4, 5, 6, 7] k = 3 rightRotate(A, k) print(A) |
Output:
[5, 6, 7, 1, 2, 3, 4]
The time complexity of the above solution is O(n), and the auxiliary space used is O(k).
3. By reversing array
We can even solve this problem in O(n) time and O(1) extra space. The idea is to reverse the last k elements of the input array and then reverse the remaining n-k elements. Finally, get the right-rotated array by reversing the complete array.
Following is the C, Java, and Python program that demonstrates it:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <stdio.h> // Function to reverse a given subarray void reverse(int A[], int low, int high) { for (int i = low, j = high; i < j; i++, j--) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } } // Function to right-rotate an array by `k` positions void rightRotate(int A[], int k, int n) { // base case: invalid input if (k < 0 || k >= n) { return; } // Reverse the last `k` elements reverse(A, n - k, n - 1); // Reverse the first `n-k` elements reverse(A, 0, n - k - 1); // Reverse the whole array reverse(A, 0, n - 1); } int main(void) { int A[] = { 1, 2, 3, 4, 5, 6, 7 }; int k = 3; int n = sizeof(A)/sizeof(A[0]); rightRotate(A, k, n); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; } |
Output:
5, 6, 7, 1, 2, 3, 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
import java.util.Arrays; class Main { // Function to exchange data of two given indices in an array public static void swap(int[] A, int i, int j) { int data = A[i]; A[i] = A[j]; A[j] = data; } // Function to reverse a given subarray public static void reverse(int[] A, int low, int high) { for (int i = low, j = high; i < j; i++, j--) { swap(A, i, j); } } // Function to right-rotate an array by `k` positions public static void rightRotate(int[] A, int k, int n) { // base case: invalid input if (k < 0 || k >= n) { return; } // Reverse the last `k` elements reverse(A, n - k, n - 1); // Reverse the first `n-k` elements reverse(A, 0, n - k - 1); // Reverse the whole array reverse(A, 0, n - 1); } public static void main(String[] args) { int[] A = { 1, 2, 3, 4, 5, 6, 7 }; int k = 3; rightRotate(A, k, A.length); System.out.println(Arrays.toString(A)); } } |
Output:
[5, 6, 7, 1, 2, 3, 4]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
# Function to exchange data of two given indices in a list def swap(A, i, j): data = A[i] A[i] = A[j] A[j] = data # Function to reverse a given sublist def reverse(A, low, high): i = low j = high while i < j: swap(A, i, j) i = i + 1 j = j - 1 # Function to right-rotate a list by `k` positions def rightRotate(A, k, n): # base case: invalid input if k < 0 or k >= n: return # Reverse the last `k` elements reverse(A, n - k, n - 1) # Reverse the first `n-k` elements reverse(A, 0, n - k - 1) # Reverse the whole list reverse(A, 0, n - 1) if __name__ == '__main__': A = [1, 2, 3, 4, 5, 6, 7] k = 3 rightRotate(A, k, len(A)) print(A) |
Output:
[5, 6, 7, 1, 2, 3, 4]
Exercise: Left rotate an array k times.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)