Sunday, April 28, 2013

Rotate an array in-place


Given an array, rotate it to the right by 'k' positions. For example, given an input array A = {1,2,3,4,5,6} and k = 4, the rotated array is {5,6,1,2,3,4}.

A straight-forward method is to have a new array R of the same size as A. Starting from the index k, copy all the elements from A to R. Then copy the elements between the indexes 0 and k-1 in A to R. This approach uses O(n) additional space.

To rotate an array in-place, we need to perform a sequence of in-place reversal operations.
Given A = {1,2,3,4,5,6} and k = 4, perform the following reversals:

Step 1: Reverse the elements between indexes 0 and k-1 in-place

4
3
2
1
5
6

Step 2: Reverse the elements between indexes k and n-1 in-place, where n is the size of A

4
3
2
1
6
5

Step 3: Reverse the entire array (between 0 and n-1) in-place

5
6
1
2
3
4

The outcome of the step 3 is the rotated array.

The time complexity of this method is O(n) with no additional space required. Here is the C++ code:

int a[] = {1,2,3,4,5,6};
int size = 6;

void Rotate(int index) {
  Reverse(0,index-1);
  Reverse(index,size-1);
  Reverse(0,size-1);
  Print();
}

void Reverse(int begin, int end) {
if(begin < 0 || end >= size) {
  return;
}
for(int i = begin, j = end; i <= j; ++i, --j) {
  int tmp;
  tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}
}

void Print() {
for(int i = 0; i < size; ++i) {
  cout << a[i] << " ";
}
}

This method does 2n swaps in all. There is a different divide-and-conquer approach which can be used to get an algorithm that does the rotate in n swaps. I will try to discuss that in a future post.

No comments:

Post a Comment