Rotate a one-dimensional array of n elements to the right by k steps.

For instance, with n=7 and k=3, the array {a, b, c, d, e, f, g} is rotated to {e, f, g, a, b, c, d}.

In my previous post we discussed about finding an element in a rotated array. You might ask, how do we rotate an array?

The straight forward way is to allocate a temporary array of size n, and then copy elements starting from index k to the new array, and copy it back to the old array. This is highly inefficient because:

- It needs extra space to store a temporary array (O(n) space).
- It involves back-and-forth copying, a total of 2*n copy operations.

So, the question is, can we do this more efficiently, preferably an in-place rotation method.

The answer is of course, yes. This is a trick so important that it becomes one of the frequently asked interview questions. An in-depth discussion is in Programming Pearls, one of the must-read book in Computer Science.

The trick is to do three reverse operation. One for the entire string, one from index 0 to k-1, and lastly index k to n-1. Magically, this will yield the correct rotated array, without any extra space! (Of course, you need a temporary variable for swapping).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void reverse_string(char* str, int left, int right) { char* p1 = str + left; char* p2 = str + right; while (p1 < p2) { char temp = *p1; *p1 = *p2; *p2 = temp; p1++; p2--; } } void rotate(char* str, int k) { int n = strlen(str); reverse_string(str, 0, n-1); reverse_string(str, 0, k-1); reverse_string(str, k, n-1); } |

I have been thinking about this problem of optimizing the rotating array for quite some time now.

The above solution is quite efficient. But wouldn't time complexity increase as the Array Size goes big?

How about just maintaining one startIndex for an Array that we can use to do the Array operations, such that as the startIndex equals the Array Length we set startIndex = 0;

The overhead is of maintaining one Start Index. This will be like an in-place rotating without actual rotation or swapping. No space required.

Following is my code, correct me on the efficiency of this method over the above approach.

Java Code:-

Integer[] tempArray = {1,2,3,4,5,6,7,8,9,10};

int shiftCountOrCurrentIndex = 4;

int arrayLength = tempArray.length;

int startIndex = 0;

int index = startIndex;

boolean takeOnce = true;

for(int cnt = 0; cnt<2;cnt++){

System.out.print("{");

while(index!=startIndex || takeOnce==true){

if(index == startIndex) takeOnce = false;

System.out.print(tempArray[index++]+",");

if((index)%arrayLength==0) index = 0;

}

System.out.println("}");

startIndex = shiftCountOrCurrentIndex;

index =startIndex;

takeOnce = true;

}

Output:-

{1,2,3,4,5,6,7,8,9,10,}

{5,6,7,8,9,10,1,2,3,4,}

-2Your solution works fine when printing the rotated array is all you needed. The problem requirement is "returning" the rotated array. That is, I passed the array into the function, and I should get the array rotated.

+1my below solution returns the sorted array and does it in N steps instead of 2N steps required by reverse_string() solution.

It move each element to it’s index + R mod MAX_ELEMENTS, and goes on to the next element.

notice that you need to check if you have completed a circle of switching elements in the array and move forward (this is handled in the last code lines of the main loop).

I would love to here your opinion on this!

void Rotate(int R, char arr[MAX])

{

if (R = MAX)

return;

int cnt = 0;

int idx = 0;

char prv = arr[idx];

for (int i = 0; i < MAX; i++)

{

char tmp = arr[(idx + R) % MAX];

arr[(idx + R) % MAX] = prv;

prv = tmp;

idx = (idx + R) % MAX;

cnt += R;

if ((cnt % MAX) == 0)

{

cnt = 0;

idx = (idx + 1) % MAX;

prv = arr[idx];

}

}

}

+3A detailed explanation of Array rotation problem with 7 possible solution with Code and Time & Space Complexities at

http://www.rawkam.com/?p=1008

-4Great job, 1337c0d3r.

One minor change: you reverse the whole string first is wrong because the location k is actually changed after reverse. You should reverse the whole string in the last.

reverse_string(str, 0, k-1);

reverse_string(str, k, n-1);

reverse_string(str, 0, n-1);

Ming

0Actually, if you reverse the string to the last, you will be rotating the array to the LEFT

0since it start from the next index of current rotate index after rotate,

the rotate should be:

rotate(0,k);

rotate(k+1,n-1);

rotate(0,n-1);

+1Ming,

I've tested the code and I verified that it is correct. It doesn't matter if the character at location k has changed. The code you showed is actually doing a rotation to the left (instead of right).

0I wrote two solutions for array rotations back in 2008. See http://ericwuyi.blogspot.com/2008/04/how-to-rotate-array.html

0One minor change: you reverse the whole string first is wrong,it should be :

reverse_string(str, 0, n-1);

reverse_string(str, 0, n-k-1);

reverse_string(str, n-k, n-1);

0how do you write this code in visual basics??

+1void RotateArray(std::vector &V,int k){

int len = V.size();

for(int index =0,key=k ;index0;index++,key–)

{

char temp = V[index];

V[index]= V[len -key];

V[len -key] = temp;

}

}

-1This is a special case of the in-place permutation. The problem becomes simple when the transformation rule is determined. For the current problem, suppose A is the array

A[i] -> A[k+1+i], if i A[i-k], if i>=k;

Then a cycle is found and the code can simply be written as

temp=A[0];

for (int i=0;i<(n-1);i++)

{

if (i=k) A[i]=A[i-k];

}

A[n-1]=temp;

0The format of the previous post is messed up.

This is a special case of the in-place permutation. The problem becomes simple when the transformation rule is determined. For the current problem, suppose A is the array, if i=k, A[i] becomes A[i-k]. Then a cycle is found and the code can simply be written as

temp=A[0];

for (int i=0;i<(n-1);i++)

{

—-

if (i=k) A[i]=A[i-k];

}

A[n-1]=temp;

-1Well, some lines of code and some sentences are always missing from my post. I don’t know what the problem is. Please delete my post.

0great idea!

I think the following reverse sequence is also OK.

assume k =3

First, reverse (0,k), we get d c b a e f g

then reverse (k+1, n-1). we get d c b a g f e

finally, reverse (0,n-1), we get e f g a b c d, which is the desired result.

0Pingback: Rotating an array | PHP Developer Resource

A detailed explanation of Array rotation problem with 7 possible solution with Code and Time & Space Complexities at

http://www.ritambhara.in/rotating-an-array-around-a-pivot/

0Pingback: Amazon interview preparation | What I learn, I blog !

It’s good but I believe we can do using only n steps instead of 2N. It’s like rotating a square matrix in place which only needs N^2 steps. you can simply track the index and the rotated index, eventually it’ll be rotated. the index will be like 0->3->6->2->5->1->4 for the above example. This is good for n%k!=0, and if n%k==0, you just need to do it iteratively like: 0->3->6->0 1->4->7->1 2->5->8->2

0just some supplement, you may need to do it iteratively even if n%k!=0 like n=6, k=4

0Store the first element of the array in a variable, and then fill current element(arr[0]) with the value of the mapping element after rotation(arr[arr.length – k]). After traverse each element of the arr, put the value of the first element to the current element. Now you have finished the rotation. It takes O(n) time. The java code:

void rotate(int[] arr, int k)

{

int first = arr[0];

int curr = 0;

int length = arr.length;

int next = length – k;

while(next != 0)

{

arr[curr] = arr[next];

curr = next;

next = curr >= k ? next – k : next – k + length;

}

arr[curr] = first;

}

0good thinking, but obviously you miss something,,,

+1Correct, when n,k has no common dividend, it works. Otherwise, need some special handling.

i.e, for n =7, any k works,

when n = 8, and k = 4, or 2, or 6, there need some improvement.

Here is my code: the oibservation is, whenever there is common divident, the index will loop back, in the case, move to next to redo loop, and altogether move n times.

0code posted always messed up.

for (j = i + k; c n) j-= n;

0This solution works, but has horrible performance. While theoretically this is the best solution as it writes only once to each position, when considering the behavior of the CPU cache it is bad.

The array is written to in jumps, which causes the cache lines to be under-utilized.

I have a solution which I’ve tested and is faster, but for now I can only make it work under certain conditions, such that k < n/2 and k is multiple of (n -k). It also sort-of works if k is smaller than n/3, but then the algorithm will have some left-overs it can't do, in which case I fallback to the triple reversal method.

Still working out the details, so not posting exact code. But in general, my measurements show that being performed on many MBs of elements (and CPU cache comes into play), my code is faster by a factor of ~3-10 from your algorithm, and faster by a factor of ~1.3-2 from the triple reversal algorithm.

If anyone is reading this and is interested, I'll get my into reasonable shape to allow posting. Please reply if you find this interesting enough.

0int main()

{

char s[]={‘a’,’b’,’c’,’d’,’e’,’f’,’g’,”};

int i,j=0,k,n;

n=strlen(s);

cin>>k;

i=0;

char q=s[0];

while(j<n)

{

char p=q;

char t=s[(i+k)%n];

s[(i+k)%n]=p;

i=(i+k)%n;

q=t;

j++;

}

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

cout<<s[i];

cout<<"\n";

return 0;

}

+1void rotate_array_Left(int a[] , int b[],int k,int n)

{ int i,new;

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

{

new= (i-k%n+n)%n;

b[new]=a[i]; }

}

0Pingback: Rotating an array in place - JavaScript - GeniusCarrier

here is a a python function to rotate without writing to one location more than once, the 3 step reverse solution write to the same location more than once

00You don’t need temporary variable for swapping, for example swapping a and b

a = a + b

b = a – b

a = a – b

0Can you tell us more about this? I’d care to find out more details.

0