# 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.

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:

Output

## Reversal algorithm for Array Rotation in Python

Output

### 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,

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.