Home » Data Structure » Array Data Structure

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

C++ implementation to print left rotation of array in O(n) time and O(1) space using multiple approaches.
Submitted by Vikneshwar GK, on February 27, 2022

Consider an integer array, of size n, that has distinct elements. The task at hand is to find the left rotations of the array for the given set of k values in O(n) time and O(1) space.

Example:

Input:
array[]= {1, 2, 3, 4, 5}
k1 = 2
k2 = 1
k3 = 3

Output:
3 4 5 1 2
2 3 4 5 1
4 5 1 2 3

Input:
array[]= {30, 40, 50, 60, 70}
k1 = 2
k2 = 4 

Output:
50 60 70 30 40
70 30 40 50 60

Solution 1: Using Modulo Operator

This is a space-efficient approach that will not use a temporary array to perform the rotation for multiple k values.

Why use Modulo?

It is used when the value of k is greater than the length of the array. For instance, if the length of the array is 5 and k is 6, the final output will be the same as the output when the k value is 1. Therefore, we are performing modulo division on k by the length of the array.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to rotate the array
void leftRotate(int array[], int length, int k)
{
    int mod = k % length;

    // iterate through the array and print
    for (int i = 0; i < length; i++)
        cout << (array[(mod + i) % length]) << " ";

    cout << "\n";
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    int k[100], n;
    cout << "Enter Number of k elements: ";
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "Enter k" << i + 1 << ": ";
        cin >> k[i];
    }

    for (int i = 0; i < n; i++) {
        leftRotate(array, N, k[i]);
    }

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 2
Enter element 2: 4
Enter element 3: 8
Enter element 4: 9
Enter element 5: 10
Enter Number of k elements: 3
Enter k1: 2
Enter k2: 4
Enter k3: 1
8 9 10 2 4 
10 2 4 8 9 
4 8 9 10 2

Solution 2: Using STL

Standard Template Library is a template class in C++ that provide common programming data structures and functions. For our problem statement, we will use the rotate function, which takes 3 arguments - start position, times to be rotated, and end position.

C++ Implementation:

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

// Function to rotate the array
void leftRotate(int array[], int length, int k)
{

    // stl rotate function
    // first argument-start position
    // second argument-rotation count
    // third argument-end position
    rotate(array, array + (k % length), array + length);

    // print the array
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
    cout << "\n";
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    int k;
    cout << "Enter value of k: ";
    cin >> k;

    leftRotate(array, N, k);
    
    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 2
Enter element 2: 4
Enter element 3: 5
Enter element 4: 7
Enter element 5: 8
Enter value of k: 2
5 7 8 2 4