# Multiple left rotations of an array with O(1)

Last Updated: May 13, 2022

## Rotations of an array with O(1)

Rotations of an array with O(1) time is one of the most trivial but tricky problems. These problems can be seen in some competitive coding challenges.

To discuss the problem statement: Given an array with n elements, perform d rotations in constant time, that is O(1)

For example, if we have been given an array arr = {1,2,3,4,5} and d = 2, then after 2 rotations the array will become: {3,4,5,1,2}.

At first, the problem seems easy to solve. We can either make a separate null array and then populate the array after making the required rotations. But this is not possible in constant time, and the space complexity increases too. We might think of rotating the array in blocks instead of rotating a single element at a time. This might be a correct solution, but it is a bad solution in terms of competitive coding. In competitive coding, the coder is supposed to come up with a solution that is not only highly optimized in time constraints but also in space constraints. This article will help you develop a highly optimized solution for rotations of an array with O(1) time complexity.

Rotations of an array have many variations depending on the question. In this article, we are concentrating on rotations of an array with O(1) time. This means that the time taken to compute the rotations must be constant. The two optimized methods are-

1. Make a copy array of size 2n and work on it. The drawback of this implementation is that the value of n for small arrays won’t be problematic, but as soon as we start dealing with huge values of n, the copy array would consume too much space.

2.  Directly print the array by doing some calculations. This is the best available for the given problem as we compute the rotations in constant time. The space complexity of this implementation is O(n).

## Implementation of method-1

In this approach of rotations of an array with O(1), we get an input array arr[] of size: size. We make a copy array cpArr[] of size 2*size and copy the original array two times in cpArr[]. We call the leftRot() function for making rotations, which takes the input array, copy array, size, and the number of rotations as arguments. We declare another variable named start which stores the position from which rotations will start. Now the tricky part is to find this start index. One observation that will help to figure out the start index is that if we perform k rotations then the element in the front of the rotated array will be the element at index (k%n) where n is the size of the original array. Then we iterate throughout the loop and print it.

## Output

This solution fulfills our condition of rotations in linear time, but the space complexity of this solution is high. For small arrays, this implementation might work, but if we try to input huge arrays, the copy array will take twice the space, resulting in too much space consumption.

## Implementation of method-2

In this approach of rotations of an array with O(1) time complexity, we store an integer array arr[], of size: size, on which rots number of rotations have to be performed. To perform the rotations, we iterate from rots up to (rots+size) and print (i%size)th position of arr. In the programming regime, the modulus operator gives us the remainder of a division operation. The logic behind using the modulus operator is that on doing (i%size) we get a remainder which is the desired array index after rots rotation.

## Output

Visual explanation:

## Complexities

### Time Complexity

In the given C++ implementations, the task to find the address of the rotation takes O(1) time. The printing of array elements takes O(n) time because we have to traverse the whole array once to print all the elements. Thus overall complexity will be:

T(n) = O(n)

### Space Complexity

In the first implementation, we make a copy of the inputted array, which is twice the size of the inputted array, and make rotations in it. Thus,

Space complexity = O(2n)

In the second implementation, we directly make changes to the inputted array. Thus,

Space complexity = O(1)

Q1.) What do you mean by rotations of an array in O(1)?

Ans.) It simply means rotating a given array by a number of rotations in O(1) or linear time complexity. The solution code provided in this article is not only optimized in terms of time complexity but also in terms of space complexity.

## Key Takeaways

To summarize, this article covers the question of rotations of an array with O(1) time complexity. This type of problem has been asked in coding rounds of some famous tech companies like IBM. The article walks through two implementations of the same along with suitable explanations for better understanding. A few frequently asked questions have also been addressed at the end of the article.

Satisfied with what you learned in this article? Give it a shot yourself and try out the problem here: Left Rotations of An Array

Do you have a dream to become a great competitive coder? Check out this great course on competitive coding and turn your dreams into reality Competitive Programming Course