Reversal algorithm for right rotation of an array

Yukti Kumari
Last Updated: May 13, 2022

Introduction

Have you ever come across a problem that requires you to rotate an array in the right or left direction, and you messed up? Then you are at the right place. 

After reading this article, you will be confident to solve this and related problems flawlessly!! 

In this article, we are going to learn a very interesting Reversal Algorithm for right rotation of an array. We will analyse this algorithm on the basis of its time complexity and space complexity and finally see its implementation.

Problem Statement 

You are given an array A of size n and a number k. Right-Rotate the array k times.

Array rotation means shifting the elements of the array by the specified positions in the specified direction, which can be either left or right.

Let’s see the sample input and output to understand clearly:


Note: The value of can be less than or greater than n. When k>n, we will do k=k%n. Because rotating the array by n or a multiple of n will have no effect on the array.

The brute force approach can be, shifting all the array elements one by one towards the right. So, if we have to shift by ‘k’ places, we will be required to do the shifting k times. We know that to shift all the elements by one place towards the right is an O(n) operation. Hence, the total time complexity for shifting k elements will be O(n.k).

Can we improve our algorithm to get a better time complexity? 

The answer is Yes, and that’s where we will introduce the reversal algorithm for right rotation of the array.

The following steps are to be followed in the reversal algorithm for right rotation of array:

  1. Reverse the whole array i.e. i=0 to i=n-1
  2. Reverse the subarray from i=0 to i=k-1
  3. Reverse the subarray from i=k to i=n-1

As you can see, mainly, we are using the function of reversing the array from index=start to index=end.

So, let’s see the pseudocode for array reversal:

while(start<end)
{
swap(arr[start],arr[end]);
start++;
end--;
}

 

C++ Implementation of Reversal algorithm for right rotation of array

/* C++ code for the implementation of Reversal algorithm for right rotation of array */
#include <bits/stdc++.h>
using namespace std;

/* Function to reverse an array starting from index=start to index=end*/
void reverseArray(int arr[], int start, int end)
{
    while (start < end)
    {
        swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

/* Function which rotates the array of size n towards right by k times*/
void rightRotation(int arr[], int k, int n)
{
    reverseArray(arr, 0, n - 1);
    reverseArray(arr, 0, k - 1);
    reverseArray(arr, k, n - 1);
}

/* function to print an array of size n*/
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << "\n";
}

// Main code to test the above implementation
int main()
{
    int n = 8;                             //size of the array
    int arr[n] = {12345678}; /*initializing the array*/
    int k = 3;                             /*number of positions by which to rotate right*/
    if(k>n) k=k%n;
    cout << "Array before rotation:\n";
    printArray(arr, n);

    rightRotation(arr, k, n); /*calling the function to rightrotate the array*/
    cout << "Array after right rotation by " << k << " places:\n";
    printArray(arr, n); /*print the final array after rotation*/

    return 0;
}

 

Output

Array before rotation:
1 2 3 4 5 6 7 8
Array after right rotation by 3 places:
6 7 8 1 2 3 4 5

 

Reversal algorithm for Array Rotation in Python

# Python code for the implementation of Reversal algorithm
# for right rotation of array

# Function to reverse an array starting from index=start to index=end
def reverseArray(arr, start, end):
    while (start < end):
        temp = arr[start]
        arr[start] = arr[end]
        arr[end] = temp
        start += 1
        end = end-1

# Function which rotates the array of size n towards right by k times


def rightRotation(arr, k):
    n = len(arr)
    reverseArray(arr, 0, n-1)
    reverseArray(arr, 0, k-1)
    reverseArray(arr, k, n-1)


# Function to print an array
def printArray(arr):
    for i in range(0, len(arr)):
        print(arr[i], end=" ")
    print("\n")


# Driver code to check above implementation
arr = [12345678]
print("Array before rotation:")
printArray(arr)
rightRotation(arr, 3)  # right Rotate array by 3 places
print("Array before rotation:")
printArray(arr)

 

Output

Array before rotation:
1 2 3 4 5 6 7 8

Array before rotation:
6 7 8 1 2 3 4 5

 

Time Complexity - O(n)

The function to reverse the array is O(n), where n is the number of elements from index=start to index=end. And we call this function thrice in our algorithm. So, the total time complexity is O(n)+O(n)+O(n) which is nothing but O(n).

Hence, it has linear time complexity.

Space Complexity - O(1)

We don’t use any extra space in our algorithm, and all the reversals are performed on the input array itself. So, it has constant space complexity,

Frequently Asked Questions

  1. How to reverse an array?
    You can reverse an array either recursively or iteratively. You can read about reversing an array in detail here.
     
  2. Is it possible to reverse an array in less than O(N) time complexity?
    No, because to reverse an array you need to traverse each element of the array at least once, so the time complexity can not be less than O(N).

Key Takeaways

In this article, we dealt with the reversal algorithm for right rotation of an array by specified positions. We discussed the brute force algorithm along with its time complexity.  Then we saw how with the use of this algorithm, the time complexity improved to O(n), and we ended up with a highly optimised implementation.

Arrays are one of the most basic data structures and there are varieties of problems related to arrays that are commonly asked in interviews.

So, strengthen your concepts by solving  Commonly asked interview questions on arrays.

Also, you can learn more about arrays here.

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think