Program to Left Rotate an Array by K Places.

Given an integer array arr[] of size n, the task is to rotate the array to the left by K steps, where K is a non-negative number.

Example:

Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}  K = 3
Output: arr[] = {4, 5, 6, 7, 8, 1, 2, 3}

Input: arr[] = {4, 6, 1, 5, 2, -2}  k = 2
Output: arr[] = {1, 5, 2, -2, 4, 6}

There are multiple approaches to rotating an array and here we are going to discuss each of them one by one in detail.

Key Note: When the number of rotations (K) is greater than the size of the array (n) for a left rotation, we can handle it by taking the effective number of rotations, which is K % n. This is because, after every n rotation, the array comes back to its original position. So, rotating by K % n is equivalent to rotating by K. (alert-passed)

Approach 1: Brute Force Approach.

This approach takes a straightforward but less efficient approach. It involves repeatedly shifting the entire array to the left by one position K times. While conceptually simple, this method has a time complexity of O(n * k), making it less suitable for large arrays or a high number of rotations.

Step-by-step algorithm:

Store the first element in a temporary variable.
Shift all elements in the array to the left by one position.
Place the temporary variable at the end of the array.
Repeat steps 1-3 for K times.

Below is the C++ code implementation of the above approach:

// C++ code to left rotate array by k position 
#include <iostream>
using namespace std;

// function to left rotate an array
void rotateLeftBruteForce(int arr[], int n, int k) {
    for (int i = 0; i < k; ++i) {
        int temp = arr[0];
        for (int j = 1; j < n; ++j) {
            arr[j - 1] = arr[j];
        }
        arr[n - 1] = temp;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    rotateLeftBruteForce(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

3 4 5 6 7 1 2

Time Complexity: O(n * k) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

Space Complexity: O(1) no extra space is required to solve this problem using the above approach.

Approach 2: Using Extra Space.

In this approach, an auxiliary array is utilized to store the first K elements of the original array. The remaining elements are then shifted to the left in the original array, and the elements from the auxiliary array are placed at the end.

Step-by-step algorithm:

Create an auxiliary array of size K.
Copy the first K elements of the original array to the auxiliary array.
Shift the remaining elements in the original array to the left by K positions.
Copy the elements from the auxiliary array to the end of the original array.

Below is the C++ code implementation for the above approach:

// C++ code to left rotate an array using extra space
#include <iostream>
using namespace std;

void rotateLeftExtraArray(int arr[], int n, int k) {
    // Check for the case where k is greater than n
    k = k % n;

    // Create an auxiliary array
    int temp[k];

    // Copy the first k elements to the auxiliary array
    for (int i = 0; i < k; ++i) {
        temp[i] = arr[i];
    }

    // Shift the remaining elements

    // in the original array to the left
    for (int i = k; i < n; ++i) {
        arr[i - k] = arr[i];
    }

    // Copy the elements from the auxiliary array

    // to the end of the original array
    for (int i = 0; i < k; ++i) {
        arr[n - k + i] = temp[i];
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    rotateLeftExtraArray(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

4 5 6 7 1 2 3

Time Complexity: O(n) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

Space Complexity: O(k) k is the size of an auxiliary array that is used in the above algorithm to rotate the array.

Approach 3: Reversal Algorithm.

The Reversal Algorithm reverses specific segments of the array to achieve rotation. First, it reverses the first K elements, then the remaining elements, and finally the entire array.

Step-by-step algorithm:

Reverse the first K elements of the given array.
Reverse the remaining elements of the given array.
Reverse the entire array.

Illustration:

Below is the C++ code implementation for the above approach:

// C++ code to left rotate an array using reversal method
#include <iostream>
using namespace std;

// function to reverse array
void reverseArray(int arr[], int start, int end) {
    while (start < end) {
        std::swap(arr[start], arr[end]);
        ++start;
        --end;
    }
}

// function to left rotate array
void rotateLeftReversal(int arr[], int n, int k) {
    // Check for the case where k is greater than n
    k = k % n;

    // Reverse the first k elements
    reverseArray(arr, 0, k - 1);

    // Reverse the remaining elements
    reverseArray(arr, k, n - 1);

    // Reverse the entire array
    reverseArray(arr, 0, n - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    rotateLeftReversal(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

4 5 6 7 1 2 3

Time Complexity: O(n) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

Space Complexity: O(1) as no extra space is required to resolve the problem.

Approach 4: Juggling Algorithm.

The Juggling Algorithm is an optimization over the reversal method. It uses the concept of finding the greatest common divisor (gcd) of n and k. It then iterates through sets of elements that need to be rotated together, reducing the number of swaps needed.

Step-by-step algorithm:

Find the greatest common divisor (gcd) of n and k.
Iterate through each set of elements that need to be rotated together.
Use temporary variables to swap elements within each set.

Below is the C++ code implementation for the above approach:

// C++ code to rotate array using juggling algorithm
#include <iostream>
using namespace std;

// function to find gcd
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// function to left rotate array
void rotateLeftJuggling(int arr[], int n, int k) {
    // Check for the case where k is greater than n
    k = k % n;

    // Find the greatest common divisor (gcd) of n and k
    int sets = gcd(n, k);

    for (int i = 0; i < sets; ++i) {
        int temp = arr[i];
        int j = i;

        while (true) {
            int d = (j + k) % n;
            if (d == i) {
                break;
            }
            arr[j] = arr[d];
            j = d;
        }

        arr[j] = temp;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    rotateLeftJuggling(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

4 5 6 7 1 2 3

Time Complexity: O(n) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

Space Complexity: O(1) as no extra space is required.

These are the few algorithms to left rotate an array by K position and you can choose one which is best for your requirement.

Program to Left Rotate an Array by K Places.

Approach 1: Brute Force Approach.

Approach 2: Using Extra Space.

Approach 3: Reversal Algorithm.

Approach 4: Juggling Algorithm.

No comments:

Post a Comment