Rotate an array

© Parineeth M R

Question 22. Rotate an array by k times


Consider the array {10, 20, 30, 40, 50}. Suppose we rotate the array once, we have to move the elements 10, 20, 30, 40 right by 1 position and move the last element 50 to the beginning to get {50, 10, 20, 30, 40}. So if we have an array of size n, then for 1 rotate operation we will need n moves. If we rotate the array k times then there will be k*n moves. There is a faster method for rotating an array. Let the array be A = {10, 20, 30, 40, 50} and the number of rotations k = 2. The procedure is:

1. Reverse the entire array. So we get {50, 40, 30, 20, 10}

2. Reverse the array in the region 0 to k -1. If k = 2, we reverse the region A[0] to A[1]. So we get the array {40, 50, 30, 20, 10}

3. Finally reverse the array in the region k to n-1 where n is the length of the array. If k=2, we reverse the region A[2] to A[4]. So we get the required result {40, 50, 10, 20, 30}.

With this technique, we always need 2*n moves irrespective of the value of k.

C/C++


/*Main function to rotate a 1 dimensional array
a: array which should be rotated. 
length: number of elements in the array. Should be > 0
num_rotations: how many times to rotate the array. Should be >= 0
*/
void rotate_array(int a[], int length, int num_rotations)
{
	/*Suppose an array has a length of 5, every time we rotate by 5 
	locations, we end up with the same array. So obtain num_rotations 
	value from 0 to length - 1*/
	num_rotations = num_rotations % length;

	if (num_rotations == 0)
		return;

	reverse_array(a, 0, length - 1);

	reverse_array(a, 0, num_rotations - 1);

	reverse_array(a, num_rotations, length - 1);
}



Java


/*Main function to rotate a 1 dimensional array
a: array which should be rotated. 
numRotations: how many times to rotate the array. Should be >= 0
*/
public static void rotateArray(int[] a, int numRotations) {
	int length = a.length;
	if (length == 0)
		return;

	/*Suppose an array has a length of 5, every time we rotate by 
	5 locations, we end up with the same array. So obtain numRotations 
	value from 0 to length - 1*/
	numRotations = numRotations % length;

	if (numRotations == 0)
		return;

	reverseArray(a, 0, length - 1);

	reverseArray(a, 0, numRotations - 1);

	reverseArray(a, numRotations, length - 1);
}



Python


#Main function to rotate a 1 dimensional list
#a: list which should be rotated. 
#num_rotations: how many times to rotate the list. Should be >= 0
def rotate_list(a, num_rotations) :
	length = len(a)
	if (length == 0):
		return

	#Suppose a list has a length of 5, every time we rotate by 
	#5 locations, we end up with the same list. So obtain num_rotations 
	#value from 0 to length - 1
	num_rotations = num_rotations % length

	if (num_rotations == 0):
		return

	reverse_list(a, 0, length - 1)

	reverse_list(a, 0, num_rotations - 1)

	reverse_list(a, num_rotations, length - 1)


#Helper function which reverses a list in region (low, high)
#a: list which needs to be reversed
#low: lower index of region to be reversed
#high: higher index of region to be reversed
def reverse_list(a, low, high) :
	while (low < high) :
		a[low], a[high] = a[high], a[low]
		low += 1
		high = high - 1