Print left rotation of array in O(n) time and O(1) space

Hello Everyone,

Given an array of size n and multiple values around which we need to left rotate the array. How to quickly print multiple left rotations?

Examples :

Input : arr[] = {1, 3, 5, 7, 9} k1 = 1 k2 = 3 k3 = 4 k4 = 6 Output : 3 5 7 9 1 7 9 1 3 5 9 1 3 5 7 3 5 7 9 1 Input : arr[] = {1, 3, 5, 7, 9} k1 = 14 Output : 9 1 3 5 7

We have discussed a solution in the below post.
[ Quickly find multiple left rotations of an array ]
The solution discussed above requires extra space. In this post, an optimized solution is discussed that doesn’t require extra space.

  • C++

// C++ implementation of left rotation of

// an array K number of times

#include <bits/stdc++.h>

using namespace std;

// Function to leftRotate array multiple times

void leftRotate( int arr[], int n, int k)

{

/* To get the starting point of rotated array */

int mod = k % n;

// Prints the rotated array from start position

for ( int i = 0; i < n; i++)

cout << (arr[(mod + i) % n]) << " " ;

cout << "\n" ;

}

// Driver Code

int main()

{

int arr[] = { 1, 3, 5, 7, 9 };

int n = sizeof (arr) / sizeof (arr[0]);

int k = 2;

// Function Call

leftRotate(arr, n, k);

k = 3;

// Function Call

leftRotate(arr, n, k);

k = 4;

// Function Call

leftRotate(arr, n, k);

return 0;

}

Output

5 7 9 1 3 7 9 1 3 5 9 1 3 5 7

Method II:

In the below implementation we will use Standard Template Library (STL) which will be making the solution more optimize and easy to Implement.

  • C++
  • Java
  • Python3

// C++ Implementation For Print Left Rotation Of Any Array K

// Times

#include <bits/stdc++.h>

#include <iostream>

using namespace std;

// Function For The k Times Left Rotation

void leftRotate( int arr[], int k, int n)

{

// Stl function rotates takes three parameters - the

// beginning,the position by which it should be rotated

// ,the end address of the array

// The below function will be rotating the array left

// in linear time (k%arraySize) times

rotate(arr, arr + (k % n), arr + n);

// Print the rotated array from start position

for ( int i = 0; i < n; i++)

cout << arr[i] << " " ;

cout << "\n" ;

}

// Driver program

int main()

{

int arr[] = { 1, 3, 5, 7, 9 };

int n = sizeof (arr) / sizeof (arr[0]);

int k = 2;

// Function Call

leftRotate(arr, k, n);

return 0;

}

Output

5 7 9 1 3

Note: the array itself gets updated after the rotation.