In this article, we have discussed Reversal algorithm. It is widely used for rotating arrays. This algorithm is specifically useful for rotating array by any number of places because it efficiently does the operation in O(N) time and O(1) auxiliary space. It uses the concept of reversing an array as a utility function.

Table of content:

1. Problem statement: Rotation
2. Reversal Algorithm
3. Example: Dry Run
4. Implementations of Reversal Algorithm
5. Time Complexity
6. Space Complexity

Problem statement: Rotation

Before we discuss the algorithm further, we must take a look at what is actually meant by rotating an array. An array can be rotated by any number of times, in either direction(left or right).

Suppose A = [1,2,3,4,5]

• Rotate once to the left: A = [2,3,4,5,1]
• Rotate once to the right: A = [5,1,2,3,4]
• Rotate by 3 postions to the left: A = [4,5,1,2,3]

Also, note that D rotations to the left are equivalent to N-D rotations to the right.

For, A = [1,2,3,4,5],

• Rotate 2 place to the left: A = [3,4,5,1,2].
• This is equivalent to 3 rotations to the right (N - D => 5-2 = 3): A = [3,4,5,1,2].

Reversal Algorithm

Following is the algorithm to rotate an array by 'd' places:

1. Reverse the first d elements.
2. Reverse the remaining n - d elements of the array.
3. Reverse the entire array.

Example: Dry Run

Given an array A = [2,5,1,4,7], we need to rotate it by 2 places towards the left

This means, the resulting array after rotation should be this:
A = [1,4,7,2,5]

Let's run the algorithm on this array(N = 5, d = 2):

Step 1: Reverse the first D (D = 2) elements.
A = [5,2,1,4,7]

Step 2: Reverse the remaining N - D (5 - 2 = 3) elements.
A = [5,2,7,4,1]

Step 3: Reverse the entire array.
A = [1,4,7,2,5]

Implementations of Reversal Algorithm

Following is the implementation of Reversal Algorithm to rotate an array in Java:

public static void reverse(int arr[], int i, int j)
{
    int s = i, e = j;
    while(s < e)
    {
        int temp = arr[s];
        arr[s] = arr[e];
        arr[e] = temp;
        s++;
        e--;
    }
}

public static void rotate(int arr[], int d)
{
    reverse(arr, 0, d-1);
    reverse(arr, d, n-1);
    reverse(arr, 0, n-1);
}

Following is the implementation of Reversal Algorithm to rotate an array in C++:

void reverse(int arr, int i, int j)
{
    int s = i, e = j;
    while(s < e)
    {
        int temp = arr[s];
        arr[s] = arr[e];
        arr[e] = temp;
        s++;
        e--;
    }
}

void rotate(int arr[], int n, int d)
{
    reverse(arr, 0, d-1);
    reverse(arr, d, n-1);
    reverse(arr, 0, n-1);
}

Time Complexity

Reversing an array takes O(N) time, where N = number of elements to be reversed. Reversal algorithm makes 3 calls to the reverse function and takes O(d) + O(N-d) + O(N) time, which is upper bounded by O(N).

Hence the time complexity is O(N).

Space Complexity

This algorithm does not take any extra space. The elements are reversed in place without extra space.

Hence, the space complexity is O(1).

With this article at OpenGenus, you must have the complete idea of Reversal Algorithm to rotate an array. Enjoy.