Interview Question: Rotating an array around a pivot

MCN Professionals | Interview Question of the day

Given an Array of (say) integers like below:

1 2 3 4 5 6 7 8

and an index, say, 2. Write a function which will rotate the array around index 2. i.e the output should be:

3 4 5 6 7 8 1 2 

There are many ways to perform the pivoted rotation of an array. Method-1 and 2 are not-so-efficient, look for approach 3 and 4 for a good algorithm

1. Rotate one element at a time

// d is the point (index) where we have to rotate

for(i=1; i<=d; i++)

{

    int temp = arr[0];

    for(int cnt=1; cnt<n; cnt++)

        arr[cnt-1] = arr[cnt];

    arr[n-1] = temp;

}

Time complexity: O(n * d)

Extra Space: O(1)

2. use a temporary array

1. Use a temporary array of size d and 
2. store the first d elements of original array in temporary array, 
3. shift all the elements of original array by d positions towards left
4. copy the elements of temporary array at the rear of original array

int * temparr = new int[d];

int i=0;

for(i=0; i<d; i++)

    temparr[i] = arr[i];

for(i=0; i<n-d; i++)

    arr[i] = arr[i+d];

for(; i<n; i++)

    arr[i] = temparr[i-n+d];

delete temparr;

Time Complexity: O(n)

Extra Space Used: O(d)

3. Use Vector Rotation

To learn about this method refer below link.

http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf

4. Reversal Algorithm

I find this a very interesting algorithm to rotate array. The algo is as below:

Let us write a function reverse which reverse an array between two indexes, The signature of the function will be as below:

void reverse(int *arr, int start, int end);

and it will reverse the subarray from start to end (both indexes inclusive). Its easy to implement (you have to just swap all the elements in first half of sub-array with corresponding second half element). reverse(arr, 0, n); will reverse the entire array.

Now the algorithm to rotate array will be like below:

1. reverse(arr, 0, d-1);
2. reverse(arr, d, n-1);
3. reverse(arr, 0, n-1);

i.e reverse the first half, then reverse the second half and finally reverse the entire array.

If input array is 1 2 3 4 5 6 7 8, then

 

reverse(arr, 0, 1);  // 2 1 3 4 5 6 7 8

reverse(arr, 2, 7);  // 2 1 8 7 6 5 4 3

reverse(arr, 0, 7);  // 3 4 5 6 7 8 1 2

I don't think I need to write code for this, but if you still find any difficulty, do let me know.