# Interview Questions

# Rotating an array around a pivot

- June 12, 2012
- Posted by: Kamal Rawat
- Category: Algorithms

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

### Solution:

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**

- Use a temporary array of size d and
- store the first d elements of original array in temporary array,
- shift all the elements of original array by d positions towards left
- 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:

- reverse(arr, 0, d-1);
- reverse(arr, d, n-1);
- 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.