Best Algorithm For Array Rotation

Problem Statement

Given an array, rotate the array to the left by k steps, where k is non-negative.

Example

Array Rotation : Using Extra Space

Algorithm

Complexity

Time complexity : O(n) 
Auxiliary Space : O(k)

Implementation

// Array Rotation using extra space
public static int[] leftRotate(int[] arr, int k) {
    // get the length of the array
    int n = arr.length;

    // To handle cases if k>n
    k = k % n;

    // construct an auxiliary array of size k and
    // fill it with the first k elements of the input array
    int[] aux = new int[k];
    for (int i = 0; i < k; i++) {
        aux[i] = arr[i];
    }

    // shift the remaining n-k elements of the input array at the beginning
    for (int i = k; i < n; i++) {
        arr[i - k] = arr[i];
    }

    // put the elements of the auxiliary array at their
    // correct positions in the input array
    for (int i = n - k; i < n; i++) {
        arr[i] = aux[i - (n - k)];
    }
    return arr;
}

Rotate Element One by One

Algorithm

Input arr=[1,2,3,4,5,6,7], k=3

Step 1: Store arr[0] in a temporary temp variable
arr=[1,2,3,4,5,6,7], temp=1
Step 2: Move rest of the elements of array to left by 1
arr=[2,3,4,5,6,7,_], temp=1
Step 3: Finally put temp variable to last(arr[n-1])
arr=[2,3,4,5,6,7,1], temp=1
Step 4: Repeat the above steps k times
arr=[4,5,6,7,1,2,3]

Complexity

Time complexity : O(n * d) 
Auxiliary Space : O(1)

Implementation

// Array Rotation One by One    
int[] leftRotateOneByOne(int arr[], int k) {
    int n = arr.length;
    k=k%n;
    for (int i = 0; i < k; i++) {
        int temp = arr[0];
        for (int j = 0; j < n - 1; j++) {
            arr[j] = arr[j + 1];
        }
        arr[n - 1] = temp;
    }
    return arr;
}

Juggling Algorithm

Algorithm

Divide the array into M sets, where M = GCD (n, k), then rotate the items inside each set.
The GCD(n, k) number of blocks is calculated using the array's element count (n) and the number of rotations (k) to be performed on the array.
Shifting will then occur in each block to the matching elements in the block.
After all of the items in all of the blocks have been relocated, the array will be rotated for the amount of times specified.

Let’s apply this to above example.

M = GCD(12, 3) = 3; Initial Array : 1 2 3 4 5 6 7 8 9 10 11 12
Elements are first moved in first set: 4 2 3 7 5 6 10 8 9 1 11 12
Second Set Moves : 4 5 3 7 8 6 10 11 9 1 2 12
Third Set Moves : 4 5 6 7 8 9 10 11 12 1 2 3  

Complexity

Time complexity : O(n) 
Auxiliary Space : O(1)

Implementation

// Array Rotation using JugglingAlgorithm

void jugglingAlgorithm(int arr[], int d) {
    int n = arr.length;
    d = d % n;
    int i, j, k, temp;
    int blocks = gcd(d, n);

    // Loop through each set
    for (i = 0; i < blocks; i++) {

        temp = arr[i];
        j = i;
        while (true) {
            k = j + d;
            if (k >= n)
                k = k - n;
            if (k == i)
                break;
            arr[j] = arr[k];
            j = k;
        }
        arr[j] = temp;
    }
}

// Function to get gcd of a and b
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

Reversal Algorithm

Algorithm

Let AB are the two parts of the input array where A = arr[0..k-1] and B = arr[k..n-1]. The idea of the algorithm is : 
Input arr[] = [1, 2, 3, 4, 5, 6, 7], k =3 and n = 7 

Step1: Reverse A to get ArB, where Ar is reverse of A.
arr= [3, 2, 1, 4, 5, 6, 7], A=[1,2,3], B=[4,5,6,7]
Step2: Reverse B to get ArBr, where Br is reverse of B.
arr= [3, 2, 1, 7, 6, 5, 4], A=[1,2,3], B=[4,5,6,7]
Step3: Reverse all to get (ArBr)r = BA.
arr= [4, 5, 6, 7, 1, 2, 3], A=[1,2,3], B=[4,5,6,7]

Complexity

Time complexity : O(n) 
Auxiliary Space : O(1)

Implementation

// Array Rotation using Reversal Algorithm

static void reversalAlgorithm(int arr[], int k) {
    if (k == 0)
        return;

    int n = arr.length;
    k = k % n;
    reverse(arr, 0, k - 1);
    reverse(arr, k, n - 1);
    reverse(arr, 0, n - 1);
}

// Function to reverse an array
static void reverse(int arr[], int start, int end) {
    int temp;
    while (start < end) {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}
  

Conclusion

In this article we discussed various algorithms for array rotation. And the best algorithms for array rotation based on time and space complexity are Juggling and Reversal Algorithm with time complexity of O(n) and with O(1) auxiliary space.

Got a question or just want to chat? Comment below or drop by our forums, where a bunch of the friendliest people you’ll ever run into will be happy to help you out!