def rotate(vec, r) : if r <= 0 : return vec L = len(vec) r %= L (cnt, beg) = (0, 0) while cnt < L : cur = beg tmp = vec[cur] while True : next = (cur + r) % L tmp1 = vec[next] vec[next] = tmp tmp = tmp1 cur = next cnt += 1 if cur == beg : break beg += 1 return vec

http://baibingz.wordpress.com/2012/10/26/rotate-array/ O(n) Time O(1) Space

In-place, O(n) time, O(1) space. slightly quicker than the version using replace() as it is iterating the array twice while this version does just once. void rotate_array(vector& s, int r) { if(r == 0 || s.empty() || s.size() < 2) { return; } r %= s.size(); if(r == 0) { return; } int round = 0; int loopCnt = s.size(); while(loopCnt) { int cur_idx = round; int cur_val = s[cur_idx]; while(1) { int to = (cur_idx+r) % s.size(); int tmp = s[to]; s[to] = cur_val; cur_idx = to; cur_val = tmp; loopCnt--; if(to == round) break; } round++; } }

I just took an array instead of a vector.. public static void rotateArrayByNPlaces(int oArray[], int places) { int length = oArray.length, destinationIndex = 0, startingIndex = 0, boundaryIndex = 0; int nArray[] = new int[length]; destinationIndex = places % length; boundaryIndex = destinationIndex; if(destinationIndex == 0) { printArray(oArray); } else { do { nArray[destinationIndex] = oArray[startingIndex++]; destinationIndex = (destinationIndex + 1) % length; } while(destinationIndex != boundaryIndex); printArray(nArray); } }

private static Vector rotateArray(Vector items, int r){ if(items==null){ return items; } if(r==items.size()){ return items; } LinkedList list=new LinkedList(items); for(int i=1; i (list)); }

Sorry, I misunderstood the question as left rotation, instead of right rotation.

http://ideone.com/yxWRl O(n) runtime, O(r) extra space

http://ideone.com/Gv6Lo A very nice O(n) solution with O(n) space

Using STL magic.. with O(r) extra space. void rotate(vector &vec, int r) { if(vec.size() tmp(vec.end()-r, vec.end()); vec.erase(vec.end()-r, vec.end()); vec.insert(vec.begin(), tmp.begin(), tmp.end()); }

void rotate_inplace(vint &num, int k) { //inplace rotation of array o(n) time, o(1) space int size=num.size(); if(size==0) return; //k=-k; //if you want right rotate k=k%size; k=k<0?size+k:k; if(k==0) return; int pos=0, start=0; int initial,buffer; const int offset=size-k; for(int i=0;i

the solution above is a generalized version of swap; however since the jump size was constant (=k), once we return back to starting index (after the swap circle) we can just increment the start by 1 to get new start, (i.e, in all elements were not covered already) however for a general swap you cannot do so import os import sys def unsort(array): s,f=0,float('inf') while(s%d,"%(s,f), #s has looped back to start print while s

O(n) time with O(1) space #include using namespace std; int circle_number(int n, int k) { int c = 1; int sum = k; while(sum % n != 0) { sum += k; c += 1; } return n/c; } void rotate_arr(int arr[], int n, int k) { k = k % n; if(k == 0) return; int circle_num = circle_number(n, k); int num = n / circle_num ; int tmp, prev, start; for(int i=0; i< circle_num; i++) { start = i; tmp = arr[start]; for(int j=0; j

I started with the trivial O(n) time and O(n) space algo. The best algo can do this in O(1) space.

O(n) time with O(1) space! Basically, popout the last element and insert it to the beginning! Do this r times! void rotate(vector arr, int r) { while (r--) { int temp = vector.pop_back(); vector.insert(0, temp); } }

Algorithm mentioned by Kruk is incorrect. Here is an example: Given array:{1,2,3,4,5,6,7,8,9,10} and you want to rotate 7 times. The answer is {8,9,10,1,2,3,4,5,6,7}, but the above algorithm produces {4,5,6,7,8,9,10,1,2,3}.