Arrays: Program to rotate an array to right


To rotate and array to right means to shift the elements to right.
The approach for the right rotation is an easy-to-understand method where the 'k' is the number of rotations that should be performed.
The array is rotated to right by shifting the elements of the arrays to the next element in the array.
In right rotation, the last element of the array will be shifted to the first position in the array.

 
Approach
  1. To understand the concept better, let's take an example of an array of five elements array = {10, 20, 30, 40, 50}
  2. If we rotate this array to the right by one index, every element would be moved to the right by one place.
  3. The last element after moving to the right will come at the first place of the array. So after the right rotation
    the array will look like array = {50, 10, 20, 30, 40}
 
Complexity

Time Complexity : O(n*k), where n is the number of elements in the array and k is the number of times we need to perform right rotation on the array
Since k can be at most n-1(k = k%n), the time complexity in the worst case is O(n^2)
Space Complexity : O(1) as we are not using extra space

 

Below is a sample program to illustrate Array Rotation.
We have created a class, precisely rotate right, which takes an array and number of rotations(k) as parameters.

Java Code
    import java.util.Arrays;

    class RotateRight{
       
        public static void rightRotation(int[] arr, int k) {
            k = k % arr.length;
            for(int i = 0; i < k; i++) {	
                  int j, last;		
                  last = arr[arr.length - 1];	//stores last element of the array
                  for(j = arr.length - 1; j > 0; j--) {		
                    arr[j] = arr[j - 1];	    //shift array by one position
                }		
                  arr[0] = last;        //last element is added to first position 
            }
        }
        public static void main(String[] args) {
            int[] array = {10, 20, 30, 40, 50};
     
            int k = 1;   // no of times to rotate the array
     
            System.out.println("Original Array");
            System.out.println(Arrays.toString(array));
            rightRotation(array,k);
            System.out.println("After right rotation Array");
            System.out.println(Arrays.toString(array));
      }
    }
 
Output

Original Array :
[10, 20, 30, 40, 50]
Array after right rotation :
[50, 10, 20, 30, 40]

 
Alternate Approach
import java.util.Arrays;

class RotateRight{

    public static void rotate(int[] nums, int k) {       
        // if k is more than length of array, k = k % length of array is same as running the 
        // rotation k time. so 5 % 3 = 2.
        // So rotating array 2 times is same as rotating 5 times when k is more than length
            if(k > nums.length){
                k = k % nums.length;
            }
        
        // this is the reversal algorithm
        // rotate part of array from start until leaving the last k elements
        // then rotate the last k elements
        // then rotate the complete array
            reverse(0, nums.length-1-k, nums);
            reverse(nums.length-k, nums.length-1, nums);
            reverse(0, nums.length-1, nums);
       
    }
    
    public static void reverse(int start, int end, int[] arr){
        
        while(start < end){
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            
            start++;
            end--;
        }
    }

    public static void main(String args[]){
        int [] nums = {1,2,3,4,5,6,7}; 
        int k = 3;
        System.out.println("Original Array");
        System.out.println(Arrays.toString(nums));
        rotate(nums,k);
        System.out.println("After right rotation " + k + " times");
        System.out.println(Arrays.toString(nums));

    }
    
}
 
Output

Original Array
[1, 2, 3, 4, 5, 6, 7]
After right rotation 3 times
[5, 6, 7, 1, 2, 3, 4]



Thanks for feedback.



Read More....
Check if an array is a min heap
Convert a sorted array into a binary search tree - recursive approach
Print the elements of an array
Find the kth largest element in the array
Find the kth smallest element in the array
Merge two sorted arrays