Rotating an array in place

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:

  1. It needs extra space to store a temporary array (O(n) space).
  2. 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).

VN:F [1.9.22_1171]
Rating: 4.6/5 (38 votes cast)
Rotating an array in place, 4.6 out of 5 based on 38 ratings

33 thoughts on “Rotating an array in place

  1. NightHawk

    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,}

    VA:F [1.9.22_1171]
    -2
  2. 1337c0d3r

    Your 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.

    VA:F [1.9.22_1171]
    +1
    1. Ori

      my 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];
      }

      }
      }

      VA:F [1.9.22_1171]
      +3
  3. Anonymous

    Great 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

    VA:F [1.9.22_1171]
    0
    1. sheng

      since 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);

      VA:F [1.9.22_1171]
      +1
  4. 1337c0d3r

    Ming,
    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).

    VA:F [1.9.22_1171]
    0
  5. Anonymous

    One 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);

    VA:F [1.9.22_1171]
    0
  6. lgaur

    void 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;
    }
    }

    VA:F [1.9.22_1171]
    -1
  7. quanquan

    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

    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;

    VA:F [1.9.22_1171]
    0
  8. quanquan

    The 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;

    VA:F [1.9.22_1171]
    -1
  9. quanquan

    Well, 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.

    VA:F [1.9.22_1171]
    0
  10. swang

    great 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.

    VN:F [1.9.22_1171]
    0
  11. Pingback: Rotating an array | PHP Developer Resource

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

  13. zyfo2

    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

    VA:F [1.9.22_1171]
    0
  14. Ethan

    Store 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;
    }

    VN:F [1.9.22_1171]
    0
      1. xiuyu.song

        Correct, 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.

        VN:F [1.9.22_1171]
        0
        1. David Bar

          This 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.

          VA:F [1.9.22_1171]
          0
  15. Rakesh Kumar

    int 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;
    }

    VA:F [1.9.22_1171]
    +1
  16. Pingback: Rotating an array in place - JavaScript - GeniusCarrier

  17. redshield

    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

    VA:F [1.9.22_1171]
    0
  18. Shady Abdel Ghaffar

    VA:F [1.9.22_1171]
    0
  19. Thanh Dai Nguyen

    You don’t need temporary variable for swapping, for example swapping a and b
    a = a + b
    b = a – b
    a = a – b

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*