This article is based on the topic of rotations of an array. More specifically, rotation of an array with O(1) time. Such problems are usually seen in many competitive coding challenges under various names such as simple array rotation game, left rotation of array in CPP, right rotation of array in C, etc. Reading this article will surely help you clear a few concepts and take you one step ahead towards becoming a great coder.

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-

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.

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

Without any further ado let's get into the implementation of both approaches.

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.

C++ implementation of rotations of an array with O(1)

// CPP implementation of left rotations of an array //with O(1) time and O(2n) space

#include<bits/stdc++.h> usingnamespacestd; // Fills temp[] with two copies of arr[] void copyArray(int arr[], int size, int cpArr[]) { // Store arr[] elements at i and i + n for (int i = 0; i<size; i++) cpArr[i] = cpArr[i + size] = arr[i]; } // Function to left rotate an array k times void leftRot(int arr[], int size, int rots, int cpArr[]) { int start = rots % size; for (int i = start; i < start + size; i++) cout << cpArr[i] << " "; cout << endl; } // Driver program int main() { int arr[] = {1, 2, 3, 5, 8, 13, 21}; int size = sizeof(arr) / sizeof(arr[0]); int cpArr[2*size]; //copy array twice the size of original array copyArray(arr, size, cpArr);

Array after 2 rotations: 358132112 Array after 3 rotations: 581321123 Array after 5 rotations: 132112358

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.

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.

Optimized C++ implementation of rotations of an array with O(1)

// CPP implementation of rotations of an array with O(1)

#include<iostream> usingnamespacestd;

void leftRot(int arr[], int size, int rots){ for(int i=rots; i < rots+size; i++){ cout << arr[i%size] << " "; } }

int main() { int arr[] = {1, 2, 3, 5, 8, 13, 21}; int size = sizeof(arr) / sizeof(arr[0]);

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,

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 following problems:

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