Multiple left rotations of an array with O(1)

Aditya Narayan Joardar
Last Updated: May 13, 2022

Introduction

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- 

 

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

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>
using namespace std;
 
// 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[] = {123581321};
    int size = sizeof(arr) / sizeof(arr[0]);
 
    int cpArr[2*size]; //copy array twice the size of original array
    copyArray(arr, size, cpArr);

cout << "Initial Array:  " ;
for(int i=0; i<size; i++){
cout << arr[i] << " ";
}

cout << endl << endl;

cout << "Copy Array:  " ;
for(int i=0; i<2*size; i++){
cout << cpArr[i] << " ";


cout << endl << endl;

    int rots = 2;
    cout << "Array after " << rots << " rotations:  " ;
    leftRot(arr, size, rots, cpArr);
 
    rots = 3;
    cout << "Array after " << rots << " rotations:  " ;
    leftRot(arr, size, rots, cpArr);
 
    rots = 5;
    cout << "Array after " << rots << " rotations:  " ;
    leftRot(arr, size, rots, cpArr);
 
    return 0;
}

 

 

Output

Initial Array:  1 2 3 5 8 13 21

Copy Array:  1 2 3 5 8 13 21 1 2 3 5 8 13 21

Array after 2 rotations:  3 5 8 13 21 1 2
Array after 3 rotations:  5 8 13 21 1 2 3
Array after 5 rotations:  13 21 1 2 3 5 8

 

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.

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

 

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


#include<iostream>
using namespace std;

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


int main()
{
int arr[] = {123581321};
int size = sizeof(arr) / sizeof(arr[0]);

cout << "Initial Array:  " ;
for(int i=0; i<size; i++){
cout << arr[i] << " ";
}


cout << endl;

int rots = 2;
cout << "Array after " << rots << " rotations:  " ;
leftRot(arr, size, rots);
cout << endl;

rots = 3;
cout << "Array after " << rots << " rotations:  " ;
leftRot(arr, size, rots);
cout << endl;

rots = 5;
cout << "Array after " << rots << " rotations:  " ;
leftRot(arr, size, rots);
cout << endl;

return 0;
}

 

Output

Initial Array:  1 2 3 5 8 13 21
Array after 2 rotations:  3 5 8 13 21 1 2
Array after 3 rotations:  5 8 13 21 1 2 3
Array after 5 rotations:  13 21 1 2 3 5 8

 

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)

 

Frequently Asked Questions

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   

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think