Rotate an array by K positions

In this tutorial, we will see how to rotate an array be K positions.

Problem:

N=6 and k=2
If Arr[] = {1, 2, 3, 4, 5, 6} and k=2
then rotated array will be  {5, 6, 1, 2,  3,  4}

Solution:

There are multiple ways to solve this problem.

Approach 1:

Move each number by 1 place and do it k times.
public static int[] rotateBruteForce(int[] nums, int k) {
		for (int i = 0; i < k; i++) {	
			for (int j = nums.length - 1; j > 0; j--) {
				// move each number by 1 place
				int temp = nums[j];
				nums[j] = nums[j - 1];
				nums[j - 1] = temp;
			}
                        System.out.println("Array rotation after "+(i+1)+" step");
			printArray(nums);
			System.out.println();
		}
        return nums;
    }
Time complexity: o(n*k)
Where n is number of elements and k denotes position shift.
Space complexity: o(1)

Approach 2:

You can rotate the array using temp array in o(n).
	public static int[] rotateExtraSpace(int[] nums, int k)
	{
		int n=nums.length;
		if(k > n) 
	        k=k%n;
	 
	    int[] result = new int[n];
	 
	    for(int i=0; i < k; i++){
	        result[i] = nums[n-k+i];
	    }
	 
	    int index=0;
	    for(int i=k; i<n; i++){
	        result[i] = nums[index++];
	    }
	    return result;
	}
Time complexity: o(n)
Space complexity: o(n)

Approach 3: 

This is the most optimized approach.
Algorithm for this approach works as below:
  • Reverse whole array.
  • Reverse first k elements
  • Reverse rest n-k elements.
For example:
let's say Array is {1,2,3,4,5,6,7,8}
You want to rotate by k position.
It will work as below:
  • You rotate the whole array. So array became: {8,7,6,5,4,3,2,1}
  • Reverse first k elements, so array became : {7,8,6,5,4,3,2,1}
  • Reverse rest of elements, so array became  : {7,8,1,2,3,4,5,6}
Java code:
public static int[] rotateOptimized(int[] nums,int k)
	{
		int n=nums.length;
		if(k > n) 
	        k=k%n;
		nums=reverse(nums,0,n-1);
		nums=reverse(nums,0,k-1);
		nums=reverse(nums,k,n-1);
		return nums;
	}
	public static int[] reverse(int[] nums,int start,int end)
	{
	
		while (start <= end ) {
			int temp=nums[start];
			nums[start]=nums[end];
			nums[end]=temp;
			start++;
			end--;
		}
		return nums;
	}
Time complexity: o(n)
Space complexity: o(1)

Complete Java program to rotate array by K positions:

package org.arpit.java2blog;

public class RotateArrayMain {

	public static void main(String[] args)
	{
		int nums[]={1,2,3,4,5,6,7,8};
		
		System.out.println("Rotate array by shifting one elements by 1 and do it k times");
		int[] result1=rotateBruteForce(nums,2);
		System.out.println("Final rotated array :");
		printArray(result1);
		System.out.println();
		System.out.println("================================");
		System.out.println("Rotate array using extra space");
		
		int nums2[]={10,20,30,40,50,60};
		int[] result2=rotateExtraSpace(nums2,5);
		printArray(result2);
		System.out.println();
		System.out.println("================================");
		System.out.println("Rotate array most optimized approach");
		int nums3[]={1,2,3,4,5,6,7,8,9,10};
		int[] result3=rotateOptimized(nums3,4);
		printArray(result3);
	}
	
	
	public static int[] rotateBruteForce(int[] nums, int k) {
		int n=nums.length;
		if(k > n) 
	        k=k%n;
		for (int i = 0; i < k; i++) {
			for (int j = n - 1; j > 0; j--) {
				// move each number by 1 place
				int temp = nums[j];
				nums[j] = nums[j - 1];
				nums[j - 1] = temp;
			}
		System.out.println("Array rotation after "+(i+1)+" step");
			printArray(nums);
			System.out.println();
		}
        return nums;
    }
	
	public static int[] rotateExtraSpace(int[] nums, int k)
	{
		int n=nums.length;
		if(k > n) 
	        k=k%n;
	 
	    int[] result = new int[n];
	 
	    for(int i=0; i < k; i++){
	        result[i] = nums[n-k+i];
	    }
	 
	    int index=0;
	    for(int i=k; i<n; i++){
	        result[i] = nums[index++];
	    }
	    return result;
	}
	
	public static int[] rotateOptimized(int[] nums,int k)
	{
		int n=nums.length;
		if(k > n) 
	        k=k%n;
		nums=reverse(nums,0,n-1);
		nums=reverse(nums,0,k-1);
		nums=reverse(nums,k,n-1);
		return nums;
	}
	public static int[] reverse(int[] nums,int start,int end)
	{
	
		while (start <= end ) {
			int temp=nums[start];
			nums[start]=nums[end];
			nums[end]=temp;
			start++;
			end--;
		}
		return nums;
	}
	
	public static void printArray(int []arr)
	{
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
	}
}
When you run above program, you will get below output:
Rotate array by shifting one elements by 1 and do it k times
Array rotation after 1 step
8 1 2 3 4 5 6 7 
Array rotation after 2 step
7 8 1 2 3 4 5 6 
Final rotated array :
7 8 1 2 3 4 5 6 
================================
Rotate array using extra space
20 30 40 50 60 10 
================================
Rotate array most optimized approach
7 8 9 10 1 2 3 4 5 6 

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012