In this article, we have explained Juggling algorithm for array rotation which is a good alternative to other rotation techniques like Reversal Algorithm and Block Swap Algorithm.

Table of contents:

1. Introduction to Array Rotation
2. Juggling algorithm
3. Example: Dry Run
4. Implementation of Juggling algorithm
5. Time & Space Complexity of Juggling algorithm

Pre-requisite: Other Array Rotation techniques, Basics of Array

Let us get started with Juggling algorithm for array rotation.

Introduction to Array Rotation

Rotating an array is a widely used operation and there exist multiple ways to do so. We have discussed a few earlier. You can check those articles here (Reversal Algorithm Block Swap Algorithm ).

We will be discussing another approach to rotate an array which is called the juggling algorithm.

Juggling algorithm

Before we discuss the algorithm in depth, let's take a look at a simple approach which will come handy in understanding the algorithm better.

If we need to rotate the array d times, we can do this by calling a function that rotates the array by 1 position. We simply store the first elemnt of the array in a temporary variable and then move all the elements ahead by one position (arr[i-1] = arr[i]). This function will require O(N) time and O(1) auxiliary space. Hence, if we call this function d times, the time complexity will become O(N * d).

Juggling algorithm is an improvement to this technique.

Steps in Juggling algorithm are:

1. We divide the array into GCD(n,d) parts and apply the above mentioned technique.
2. The first elements from each set are rotated. This makes the first element of set as the first element of the last set. The 1st element of the 2nd set becomes the first element of the first set and so on.
3. Next, the second elements are rotated in a similar fashion.

Example: Dry Run

Let arr = [1,2,3,4,5,6], n = 6, d = 2
GCD(6,2) = 2

We divide the array into 3 parts (each of size 2) => arr[] = [1,2,3,4,5,6]

First Pass: Swap elements at indices such that

• temp = arr[0]
• arr[0] = arr[2]
• arr[2] = arr[4]
• arr[4] = temp

arr[] = [3,2,5,4,1,6]

Second Pass: Swap elements such that

• temp = arr[1]
• arr[1] = arr[3]
• arr[3] = arr[5]
• arr[5] = temp

arr[] = [3,4,5,6,1,2]

Implementation of Juggling algorithm

Following is the implementation in Java:

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
void leftRotate(int arr[], int d, int n)
{
    d = d % n;
    int g = gcd(d, n);
    for (int i = 0; i < g; i++) 
    {
        int temp = arr[i];
        int j = i;
        while (1) 
        {
            int k = j + d;
            if (k >= n)
                k = k - n;

            if (k == i)
                break;

            arr[j] = arr[k];
            j = k;
        }
        arr[j] = temp;
    }
}

Time & Space Complexity of Juggling algorithm

Time Complexity

The time complexity is O(N) where N is the size of the array. Every element is swapped at most once, hence, the time complexity is upper bound by O(N).

Space Complexity

This algorithm does not require any auxiliary space, hence, the space complexity is constant, O(1).

With this article at OpenGenus, you must have the complete idea of Juggling algorithm.