How to rotate an array?

I have the following problem to test:

Rotate an array of n elements to the right by k steps.

For instance, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to
[5,6,7,1,2,3,4]. How many different ways do you know to solve this problem?

My solution in intermediate array:

With Space is O(n) and time is O(n), I can create a new array and then copy elements to the new array. Then change the original array by using System.arraycopy().

O(n)

O(n)

System.arraycopy()

public void rotate(int nums, int k) {
if(k > nums.length)
k=k%nums.length;

int result = new int[nums.length];

for(int i=0; i < k; i++){
result[i] = nums[nums.length-k+i];
}

int j=0;
for(int i=k; i<nums.length; i++){
result[i] = nums[j];
j++;
}

System.arraycopy( result, 0, nums, 0, nums.length );
}


But is there a better way we can do it with bubble rotate(like bubble sort) in O(1) space?

O(1

n = 5

k = 2

15 Answers
15

You don't need the for- loops.

for

public int rotate(int nums, int k) {
if(k > nums.length)
k=k%nums.length;

int result = new int[nums.length];
System.arraycopy( nums, k+1, result, 0, k );
System.arraycopy( nums, 0, result, k+1, nums.length-1 );

//Case 1: The rotated array will be assigned to the given array "nums"
nums = result;

return result; //Case 2: method returns the rotated array
}


Specification of arraycopy can be found here http://docs.oracle.com/javase/7/docs/api/java/lang/System.html

Not testet. The overall complexity of method rotate O(1).

If your question was about all possible permutation have a look here
Java Code for permutations of a list of numbers

Another advise is to check out the Java Collection API which provides many sophisticated data structures and common sort algorithms, which are all implemented in a very efficient way.

EDIT due to comment.

The method returns a rotated array. You can use the method within an outer method like this: (Just pseudo-code)

void rotator(int nums) {
int rotated = nums;
//Can be invoked iteraritve or within a loop like this
rotated = rotate(rotated, 3);
}


nums

System.arraycopy

Method 1 - The Reversal Algorithm(Good One):

Algorithm:

rotate(arr, d, n)

reverse(arr, l, n);

reverse(arr, 1, n-d) ;

reverse(arr, n - d + 1, n);

Let AB are the two parts of the input array where A = arr[0..n-d-1] and B = arr[n-d..n-1]. The idea of the algorithm is:

Reverse all to get (AB) r = BrAr.

Reverse A to get BrA. /* Ar is reverse of A */

Reverse B to get BA. /* Br is reverse of B */

For arr = [1, 2, 3, 4, 5, 6, 7], d =2 and n = 7

A = [1, 2, 3, 4, 5] and B = [ 6, 7]

Reverse all, we get BrAr = [7, 6, 5, 4, 3, 2, 1]

Reverse A, we get ArB = [7, 6, 1, 2, 3, 4, 5]
Reverse B, we get ArBr = [6, 7, 5, 4, 3, 1, 2]

Here is the Code Snippet:

void righttRotate(int arr, int d, int n)
{
reverseArray(arr, 0, n-1);
reverseArray(arr, 0, n-d-1);
reverseArray(arr, n-d, n-1);
}

void reverseArray(int arr, int start, int end)
{
int i;
int temp;
while(start < end)
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}


Method 2 - A Juggling Algorithm

Divide the array in different sets where number of sets is equal to GCD of n and d and move the elements within sets.

If GCD is 1, then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

Here is an example for n =12 and d = 3. GCD is 3 and

Let arr be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

Elements are first moved in first set
arr after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

Then in second set.
arr after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

Finally in third set.
arr after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

Here is the code:

void leftRotate(int arr, int d, int n)
{
int i, j, k, temp;
int gcd = gcd(d, n);
for (i = 0; i < gcd; i++)
{
/* move i-th values of blocks */
temp = arr[i];
j = i;
while(1)
{
k = j + d;
if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}

int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}


Time complexity: O(n)

Auxiliary Space: O(1)

Method 3 - Rotate one by one:

righttRotate(arr, d, n)

start

For i = 0 to i < d

Right rotate all elements of arr by one

end

To rotate by one, store arr[n-1] in a temporary variable temp, move arr[1] to arr[2], arr[2] to arr[3] …and finally temp to arr[0]

Let us take the same example arr = [1, 2, 3, 4, 5, 6, 7], d = 2, rotate arr by one 2 times. We get [7, 1, 2, 3, 4, 5, 6] after first rotation and [ 6, 7, 1, 2, 3, 4, 5] after second rotation.

Her is Code Snippet:

void leftRotate(int arr, int d, int n)
{
int i;
for (i = 0; i < d; i++)
leftRotatebyOne(arr, n);
}

void leftRotatebyOne(int arr, int n)
{
int i, temp;
temp = arr[n-n];
for (i = 0; i < n-1; i++)
arr[i] = arr[i+1];
arr[n - 1] = temp;
}


Time complexity: O(n*d)

Auxiliary Space: O(1)

The following code will do your job. This is for right rotate.

public void rightrotate(int nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}

public void reverse(int nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}


If you want to do left rotate just use the following

public void leftrotate(int nums, int k) {
k %= nums.length;
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
reverse(nums, 0, nums.length - 1);
}


Space is O(1) and time is O(n)

static void rotate(int array, int k) {
int size = array.length;
if (size <= 1) return;
k = k % size;
if (k == 0) return;
for (int i = 0, start = 0, from = 0, to = -1, move = array[0]; i < size; ++i, from = to) {
to = (from + k) % size;
int temp = array[to];
array[to] = move;
move = to == start ? array[to = ++start] : temp;
}
}


Partial Code for ONE time array rotation

last=number_holder[n-1];
first=number_holder[0];
//rotation

number_holder[0]=last;

for(i=1;i<n;i++)
{
last=number_holder[i];
number_holder[i]=first;
first=last;
}


Display the array

for(i=1;i<n;i++)
{
System.out.println(number_holder[i]);
}


This is a simple solution to rotate an array.

public class ArrayRotate {
public int rotateArray(int array, int k) {

int newArray = new int[array.length];
for (int i = 0; i < array.length; i++) {
newArray[(i + k) % array.length] = array[i];
}
System.arraycopy(newArray, 0, array, 0, array.length);
return newArray;

}

public static void main(String args) {
int array = { 1, 2, 3, 4, 5, 6, 7 };
ArrayRotate rotate = new ArrayRotate();
rotate.display(rotate.rotateArray(array, 3));

}

public void display(int array) {
for (int i : array) {
System.out.print(i + ",");
}
}
}


Runtime complexity is O(n)

There are several other algorithm to achieve the same.

This solution is O(1) space and O(N) time. It is in C#, takes an array parameter and rotates it in place. The algorithm goes through the first s (the shift) elements, starting with the first element moves it to the s_th position, then moves the s_th to the 2s_th position etc. If each of the first s elements rotates back to itself then there will be (arrayLength / s) * s = arrayLength loops, and at the end the array will be rotated by s. If the first s elements do not rotate back themselves, then there will still be cycles, say if s = 4, there could be one cycle which is 1-3-1 and the second 2-4-2, the line - if (ind == indAtBeg), checks for a cycle and terminates the while loop. The variable loopCount increments, when there is a rotation starting at any of the first s elements.

public static void rotateArrayByS(int ar, int s)
{
int len = ar.Length, ind = 0, temp1 = ar[0],
temp2 /*temp1 and temp2 for switching elements*/,
loopCount /*rotations starting at the first s elemtns of ar*/ = 0;

s %= len;

while (loopCount < s)
{
int indAtBeg = ind;
temp1 = ar[ind];

bool done = false;
while (!done)
{
if (ind < s)
loopCount++;

ind = (ind + s) % len;

//cycle detected
if (ind == indAtBeg)
done = true;

//switch the elements
temp2 = ar[ind];
ar[ind] = temp1;
temp1 = temp2;
}

++ind;
}
}


ArrayUtil class is used to provide following utilities in primitive array

Algorithm for array rotation by shift-

Space Complexity: In-place Algorithm, No extra space needed so O(1).

Time Complexity : Array reversal of size k take O(k/2) i.e swapping k/2 pairs of elements.

Array Reversal time- O(k) for k size array.

Total time in Rotation-

public class Solution {

public static void main(String args) {
int k = 3;
int a = {1,2,3,4,5,6,7};

ArrayUtil.leftRotate(a, k);

for (int i : a)
System.out.println(i);
}
}

class ArrayUtil {

public static final boolean checkIndexOutOfRange(int array, int index) {
if (index < 0 || index > array.length)
return true;
return false;
}

public static final void swap(int array, int i, int j) {
if (checkIndexOutOfRange(array, i) || checkIndexOutOfRange(array, j))
return;
int t = array[i];
array[i] = array[j];
array[j] = t;
}

public static final void reverse(int array, int startIndex, int endIndex) {
if (checkIndexOutOfRange(array, startIndex) || checkIndexOutOfRange(array, endIndex))
return;
while (startIndex < endIndex) {
swap(array, startIndex, endIndex);
startIndex++;
endIndex--;
}
}

public static final void reverse(int array) {
reverse(array, 0, array.length - 1);
}

public static final void leftRotate(int array, int shift) {
int arrayLength = array.length;
if (shift >= arrayLength)
shift %= arrayLength;
reverse(array, 0, shift - 1);
reverse(array, shift, arrayLength - 1);
reverse(array);
}
}


AFAIK, there are three ways to rotate an array with O(1) extra space, or put it another way, to swap two contiguous subarray.

C++ has builtin function std::rotate(), which takes three iterator first, middle, last,
and return new_middle, which is where the old first element lies in the rotated
sequence.

std::rotate()

first, middle, last

new_middle

I have checked the implementation on my computer, which use second approach I listed above.
(line 1246 in /usr/lib/gcc/i686-pc-cygwin/5.4.0/include/c++/bits/stl_algo.h).

/usr/lib/gcc/i686-pc-cygwin/5.4.0/include/c++/bits/stl_algo.h

Below is my implementation of rotate, with test program.

#include <iostream>
#include <vector>

// same logic with STL implementation, but simpler, since no return value needed.
template <typename Iterator>
void rotate_by_gcd_like_swap(Iterator first, Iterator mid, Iterator last) {
if (first == mid) return;
Iterator old = mid;
for (; mid != last;) {
std::iter_swap(first, mid);
++first, ++mid;
if (first == old) old = mid; // left half exhausted
else if (mid == last) mid = old;
}
}

// same logic with STL implementation
template <typename Iterator>
Iterator rotate_by_gcd_like_swap_then_return_new_mid(Iterator first, Iterator mid, Iterator last) {
if (first == mid) return last;
if (mid == last) return first;
Iterator old = mid;
for(;;) {
std::iter_swap(first, mid);
++first, ++mid;
if (first == old) old = mid;
if (mid == last) break;
}
Iterator result = first; // when first time `mid == last`, the position of `first` is the new `mid`.
for (mid = old; mid != last;) {
std::iter_swap(first, mid);
++first, ++mid;
if (first == old) old = mid;
else if (mid == last) mid = old;
}
return result;
}

int main() {
using std::cout;
std::vector<int> v {0,1,2,3,4,5,6,7,8,9};
cout << "before rotate: ";
for (auto x: v) cout << x << ' '; cout << 'n';
int k = 7;
rotate_by_gcd_like_swap(v.begin(), v.begin() + k, v.end());
cout << " after rotate: ";
for (auto x: v) cout << x << ' '; cout << 'n';
cout << "sz = " << v.size() << ", k = " << k << 'n';
}


Above solutions talk about shifting array elements either by reversing them or any other alternative.

I've unique solution. How about determining the starting position of element after n rotations. Once we know that, then simply insert elements from that index and increment counter using modulus operation. Using this method we can avoid using extra array operations and so on.

Here is my code:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void rotateLeft(int n,int r) {
vector<long int> vec(n);
int j = n;
// get the position of starting index after r left rotations.
while(r!=0) {
--j;
if(j==0)
j = n;
--r;
}
for(long int i=0;i<n;++i) {
// simply read the input from there and increment j using modulus operator.
cin>>vec[j];
j = (j+1)%n;
}
// print the array
for(long int i=0;i<n;++i)
cout<<vec[i]<<" ";
}
int rotateRight (int n,int r) {
// get the position of starting index after r left rotations.
int j = r % n;

vector<long int> vec(n);
for(int i=0;i<n;i++) {
cin>>vec[j];
j=(j+1)%n;
}
for(int i=0;i<n;i++)
cout<<vec[i]<<" ";

}
int main() {

long int n,r; // n stands from number of elements in array and r stands for rotations.
cin>>n>>r;
// Time Complexity: O(n+r) Space Complexity: O(1)
rotateLeft(n,r);
// Time Complexity: O(n) Space Complexity: O(1)
rotateRight(n,r);
return 0;

}


#include <stdio.h>

int
main(void)
{
int arr[7] = {1,2,3,4,5,6,7};
int new_arr[7] = {0};
int k = 3;
int len = 7;
int i=0;

for (i = (len-1); i>=0; i--) {
if ((i+k) >= len) {
new_arr[(i+k-len)] = arr[i];
} else {
new_arr[(i+k)] = arr[i];
}
}

for (i=0;i<len;i++) {
printf("%d ", new_arr[i]);
}

return 0;
}


Time complexity O(n)
Space complexity O(2*n).

Thanks.

Here is the complete Java code for left and right array rotation by k steps

import java.util.*;

public class ArrayRotation {
private static Scanner sc;

public static void main(String args) {
int n,k;
sc = new Scanner(System.in);
System.out.print("Enter the size of array: ");
n = sc.nextInt();

int a = new int[n];
System.out.print("Enter the "+n+" elements in the list: ");
for(int i=0;i<n;i++)
a[i] = sc.nextInt();

System.out.print("Enter the number of left shifts to array: ");
k = sc.nextInt();

System.out.print("Array before "+k+" shifts: ");
display(a);

leftRoation(a,k);
System.out.println();

System.out.print("Array after "+k+" left shifts: ");
display(a);

rightRoation(a,k);
System.out.println();

System.out.print("Array after "+k+" right shifts: ");
display(a);
}

public static void leftRoation(int a, int k){
int temp=0, j;
for(int i=0;i<k;i++){
temp = a[0];
// j=0; // both codes work i.e. for loop and while loop as well
// while(j<a.length-1){
// a[j]=a[j+1];
// j++;
// }
for(j=0;j<a.length-1;j++)
a[j]=a[j+1];
a[j]=temp;
}
}

public static void rightRoation(int a, int k){
int temp=0, j;
for(int i=0;i<k;i++){
temp = a[a.length-1];
for(j=a.length-1;j>0;j--)
a[j]=a[j-1];
a[j]=temp;
}
}

public static void display(int a){
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
}
}

/****************** Output ********************
Enter the size of array: 5
Enter the 5 elements in the list: 1 2 3 4 5
Enter the number of left and right shifts to array: 2
Array before 2 shifts: 1 2 3 4 5
Array after 2 left shifts: 3 4 5 1 2
Array after 2 right shifts: 1 2 3 4 5 // here the left shifted array is taken as input and hence after right shift it looks same as original array.
**********************************************/


Python code:

def reverse(arr,start , end):
while(start <= end):
arr[start] , arr[end] = arr[end] , arr[start]
start = start+1
end = end-1

arr = [1,2,3,4,5,6,7]
n = 7
k = 2
reverse(arr,0,n-1)
# [7,6,5,4,3,2,1]
reverse(arr,0,n-1-k)
# [3,4,5,6,7,2,1]
reverse(arr,n-k,n-1)
# [3,4,5,6,7,1,2]

print arr
# [3, 4, 5, 6, 7, 8, 9, 1, 2]


My solution... (a: the array, n : size of array, k: number of shifts) :

public static int arrayLeftRotation(int a, int n, int k) {

if (k == 0) return a;

for (int i = 0; i < k; i++) {
int retenue = a[0];
int copie = java.util.Arrays.copyOfRange(a, 1, n );
for (int y = 0; y <= copie.length - 1 ; y++) {
a[y] = copie[y];
}
a[n-1] = retenue;
}
return a;
}


In Ruby Its very simple, Please take a look, Its one line.

def array_rotate(arr)
i, j = arr.length - 1, 0
arr[j],arr[i], i, j = arr[i], arr[j], i - 1, j + 1 while(j<arr.length/2)
puts "#{arr}"
end


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.