Introduction
An array is a collection of elements of similar data types. We can have an array of integers or characters or structures etc. In this blog, we are going to learn about the circular right rotation of an array. Now you must be wondering what is meant by right rotation!! The right rotation of an array implies that you have to rotate the array towards the right, i.e., clockwise rotation of an array. This is the most common problem asked by interviewers, so read all the concepts discussed here carefully.
Problem: You are given an array of integers, circularly rotate the array to the right by one.
Let’s understand the problem more clearly with the below example.
Suppose you are given an array arr of integers.
1 | 2 | 3 | 4 | 5 | 6 |
Now you have to rotate the array clockwise by one. So you have to produce output as:-
6 | 1 | 2 | 3 | 4 | 5 |
Now you’re clear with the problem statement so let’s move towards solving it.
Method 1: Using Loops
To rotate the array circularly, we can use loops. Let’s discuss the steps first then we will move towards code.
Step 1: Store the last element of the array in a variable temp.
Step 2: All the elements of the array will be shifted by one towards the right.
Step 3: Replace the first element of the array with the value stored in temp.
Java program for Circular Right Rotation of an Array
import java.util.Arrays; public class Rotating { static int arr[] = new int[] {1,2,3,4,5,6}; // Function for rotating the array static void rotateRight() { int temp = arr[arr.length - 1]; //shifting the array elements by one for (int i = arr.length - 1; i > 0; i--) arr[i] = arr[i - 1]; //Replacing the first array element by temp arr[0] = temp; } public static void main(String[] args) { System.out.println("Array given in input is:"); System.out.println(Arrays.toString(arr)); rotateRight(); System.out.println("Array after rotation is:"); System.out.println(Arrays.toString(arr)); } } Output: Array given in input is 1 2 3 4 5 6 Array after rotation is 6 1 2 3 4 5
C++ program for Circular Right Rotation Of an Array
#include <iostream> using namespace std; void rotateRight(int * arr, int n) { int temp = arr[n - 1]; //shifting the array elements by one for (int i = n - 1; i > 0; i--) arr[i] = arr[i - 1]; //Replacing the first array element by temp arr[0] = temp; } int main() { int arr[] = {1,2,3,4,5,6}; int n = sizeof(arr) / sizeof(arr[0]); printf("Array given in input is\n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); rotateRight(arr, n); printf("\nArray after rotation is\n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; }
Output: Array given in input is 1 2 3 4 5 6 Array after rotation is 6 1 2 3 4 5
Let’s discuss the complexities of method one:
Time Complexity: O(n), where n refers to the number of elements in the array.
You need to iterate through all the elements so time complexity is O(n).
Space Complexity: O(1) As we are not taking any extra space here.
Method 2: Using Two Pointers
We can accomplish circular right rotation of an array using two pointers, i and j. You will understand it better by going through the below steps:
Step1: Take two pointers i and j.i will point at the starting index of the array, and j will indicate at the end index of the array.
Step 2. Swap arr[i] and arr[j].
Step 3. Now move the i pointer forward and keep the j pointer fixed.
Repeat this process until i is less than j, this will ensure that the elements till index i are placed at the desired position.
Let’s code this approach now.
C++ Program for Circular Right Rotation of an Array
#include <iostream> using namespace std; //function to rotate the array clockwise void rotateRight(int arr[], int n) { //i pointing to the starting element of the array //j pointing to the last element of the array int i = 0, j = n - 1; while (i != j) { //swapping the elements swap(arr[i], arr[j]); i++; } } int main() { int arr[] = {1,2,3,4,5,6}; //finding size of the array int n = sizeof(arr) / sizeof(arr[0]); cout << "Array given as input is \n"; for (int i = 0; i < n; i++) cout << arr[i] << " "; rotateRight(arr, n); cout << "\nArray after rotation is\n"; for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; }
Output: Array given as input is 1 2 3 4 5 6 Array after rotation is 6 1 2 3 4 5
Java program for Circular Right Rotation of an Array
import java.util.Arrays; public class Rotating { static int arr[] = new int[] {1,2,3,4,5,6}; //function to rotate the array clockwise static void rotateRight() { //i pointing to the starting element of the array //j pointing to the last element of the array int i = 0, j = arr.length - 1; while (i != j) { //swapping the elements int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; } } public static void main(String[] args) { System.out.println("Array given in input is"); System.out.println(Arrays.toString(arr)); rotateRight(); System.out.println("Array after rotation is"); System.out.println(Arrays.toString(arr)); } }
Output: Array given as input is 1 2 3 4 5 6 Array after rotation is 6 1 2 3 4 5
Let’s discuss the time and space complexities of this approach.
Time Complexity: O(n), where n refers to the number of elements in the array.
You need to iterate through all the elements, so time complexity is O(n). Space Complexity: O(1) As we are not taking any extra space here.
Frequently Asked Questions
Left rotation of an array refers to the anti clockwise rotation of array elements.
Yes! You can rotate the array circularly by any number of elements you want.You can also rotate that clockwise or anticlockwise.
Yes you can rotate an array of characters with the same approach we have discussed above for an array of integers.
No, You can’t rotate an array in less than O(N) time complexity because you need to traverse the whole array for rotating an array circularly.
Key Takeaways
In this blog, we discussed two approaches for the circular right rotation of an array. The right rotation of an array implies that you have to rotate the array clockwise. You can rotate array elements circularly by any number of elements. The two-pointer approach is more accessible to implement than the first approach, but the time complexity of both methods will be O(N). After reading this blog, try to solve this problem on your own because you will become good at problem-solving only through practice. Happy Coding!
By: Deeksha Sharma
Leave a Reply