Left And Right Rotation Of Array In C++

Array rotation is a fundamental operation in computer science that involves shifting the elements of an array by a specified number of positions, either to the left or to the right. In this article, you will learn several C++ techniques for performing both left and right array rotations efficiently.

Problem Statement

Given an array and a number d, the task is to rotate the array elements to the left or right by d positions. A left rotation shifts elements to the left, with elements wrapping around from the beginning to the end. Conversely, a right rotation shifts elements to the right, with elements wrapping from the end to the beginning. This operation is crucial in various algorithms, data processing tasks, and even in puzzles or game development.

Example

Consider an array [1, 2, 3, 4, 5] of size 5.

• Left Rotation by d = 2:
• Original: [1, 2, 3, 4, 5]
• After 2 left rotations: [3, 4, 5, 1, 2]

• Right Rotation by d = 2:
• Original: [1, 2, 3, 4, 5]
• After 2 right rotations: [4, 5, 1, 2, 3]

 

Background & Knowledge Prerequisites

To understand the concepts and code examples in this article, you should have a basic understanding of:

• C++ Fundamentals: Variables, data types, basic input/output.
• Arrays: Declaration, initialization, and access to elements.
• Loops: for loops for iterating through arrays.
• Functions: Defining and calling functions in C++.

 

Use Cases or Case Studies

Array rotation finds applications in a variety of domains:

• Image Processing: Rotating pixel data for image manipulation or special effects.
• Cryptography: Certain encryption algorithms use permutations and rotations of data blocks.
• Data Buffer Management: Efficiently handling circular buffers where old data is overwritten by new data.
• Gaming: Implementing carousel-like displays, game board rotations, or character movement patterns.
• Puzzle Solving: Algorithms for puzzles like Rubik's Cube often involve array rotations to simulate moves.

 

Solution Approaches

Here, we will explore three common approaches for array rotation, detailing their implementation in C++.

Approach 1: Using a Temporary Array (Left Rotation)

This is a straightforward method where the first d elements are stored in a temporary array. The remaining N-d elements are then shifted to the beginning, and finally, the elements from the temporary array are copied to the end of the main array.

• One-line summary: Store initial elements, shift remaining, then append stored elements.

 

// Left Rotation using Temporary Array
#include <iostream>
#include <vector>
#include <algorithm> // For std::min and std::max

void rotateLeftTemp(std::vector<int>& arr, int d) {
    int n = arr.size();
    if (n == 0 || d % n == 0) return; // No rotation needed
    d = d % n; // Ensure d is within array bounds

    std::vector<int> temp(d);

    // Store the first 'd' elements in a temporary array
    for (int i = 0; i < d; ++i) {
        temp[i] = arr[i];
    }

    // Shift the remaining 'N-d' elements to the left
    for (int i = d; i < n; ++i) {
        arr[i - d] = arr[i];
    }

    // Copy the elements from the temporary array to the end
    for (int i = 0; i < d; ++i) {
        arr[n - d + i] = temp[i];
    }
}

int main() {
    // Step 1: Initialize an array and rotation amount
    std::vector<int> myArr = {1, 2, 3, 4, 5};
    int d = 2; // Number of positions to rotate left

    std::cout << "Original array: ";
    for (int x : myArr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Step 2: Perform left rotation
    rotateLeftTemp(myArr, d);

    // Step 3: Print the rotated array
    std::cout << "Array after " << d << " left rotations: ";
    for (int x : myArr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

• Sample output:

Original array: 1 2 3 4 5 
Array after 2 left rotations: 3 4 5 1 2

 

• Stepwise explanation for clarity:

1. A temporary std::vector of size d is created.
2. The first d elements of the original array are copied into this temporary vector.
3. The elements from index d to N-1 (the remaining N-d elements) are shifted d positions to the left, filling the initial d positions of the original array.
4. Finally, the elements from the temporary vector are copied back into the last d positions of the original array.

Approach 2: Rotating One-by-One (Left Rotation)

This method involves repeatedly rotating the array by one position d times. In each single rotation, the first element is saved, all other elements are shifted one position to the left, and the saved first element is placed at the end.

• One-line summary: Perform single left rotations d times.

 

// Left Rotation One-by-One
#include <iostream>
#include <vector>

// Helper function to rotate array by one position to the left
void rotateLeftByOne(std::vector<int>& arr) {
    if (arr.empty()) return;
    int firstElement = arr[0];
    for (size_t i = 0; i < arr.size() - 1; ++i) {
        arr[i] = arr[i + 1];
    }
    arr[arr.size() - 1] = firstElement;
}

void rotateLeftOneByOne(std::vector<int>& arr, int d) {
    int n = arr.size();
    if (n == 0 || d % n == 0) return;
    d = d % n;

    for (int i = 0; i < d; ++i) {
        rotateLeftByOne(arr);
    }
}

int main() {
    // Step 1: Initialize an array and rotation amount
    std::vector<int> myArr = {1, 2, 3, 4, 5};
    int d = 2; // Number of positions to rotate left

    std::cout << "Original array: ";
    for (int x : myArr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Step 2: Perform left rotation
    rotateLeftOneByOne(myArr, d);

    // Step 3: Print the rotated array
    std::cout << "Array after " << d << " left rotations: ";
    for (int x : myArr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

• Sample output:

Original array: 1 2 3 4 5 
Array after 2 left rotations: 3 4 5 1 2

 

• Stepwise explanation for clarity:

1. A helper function rotateLeftByOne is defined to perform a single left rotation. It stores the first element, shifts all subsequent elements one position left, and then places the stored first element at the end.
2. The main rotateLeftOneByOne function calls rotateLeftByOne d times to achieve the desired total rotation.

Approach 3: The Reversal Algorithm

The reversal algorithm is an efficient method for both left and right array rotations. It works by performing three reversals on parts of the array. This approach has optimal time complexity and uses minimal extra space.

• One-line summary: Three strategic reversals to achieve rotation.

 

Left Rotation using Reversal Algorithm:

To rotate an array of size N by d positions to the left:

1. Reverse the first d elements.
2. Reverse the remaining N-d elements.
3. Reverse the entire array.

 

// Left Rotation using Reversal Algorithm
#include <iostream>
#include <vector>
#include <algorithm> // For std::reverse

// Helper function to reverse a portion of an array
void reverseArray(std::vector<int>& arr, int start, int end) {
    while (start < end) {
        std::swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

void rotateLeftReversal(std::vector<int>& arr, int d) {
    int n = arr.size();
    if (n == 0 || d % n == 0) return;
    d = d % n; // Ensure d is within array bounds

    // Step 1: Reverse the first 'd' elements
    reverseArray(arr, 0, d - 1);

    // Step 2: Reverse the remaining 'N-d' elements
    reverseArray(arr, d, n - 1);

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

int main() {
    // Step 1: Initialize an array and rotation amount
    std::vector<int> myArr = {1, 2, 3, 4, 5};
    int d = 2; // Number of positions to rotate left

    std::cout << "Original array: ";
    for (int x : myArr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Step 2: Perform left rotation
    rotateLeftReversal(myArr, d);

    // Step 3: Print the rotated array
    std::cout << "Array after " << d << " left rotations: ";
    for (int x : myArr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

• Sample output:

Original array: 1 2 3 4 5 
Array after 2 left rotations: 3 4 5 1 2

 

• Stepwise explanation for clarity:

1. The reverseArray helper function is used to reverse elements within a specified range [start, end].
2. For a left rotation by d:
   • The elements from index 0 to d-1 are reversed.

• The elements from index d to N-1 are reversed.
• Finally, the entire array from 0 to N-1 is reversed. This effectively rotates the array.

Right Rotation using Reversal Algorithm:

To rotate an array of size N by d positions to the right:

1. Reverse the last d elements.
2. Reverse the first N-d elements.
3. Reverse the entire array.

Alternatively, a right rotation by d is equivalent to a left rotation by N-d.

 

// Right Rotation using Reversal Algorithm
#include <iostream>
#include <vector>
#include <algorithm> // For std::reverse

// Helper function to reverse a portion of an array
void reverseArray(std::vector<int>& arr, int start, int end) {
    while (start < end) {
        std::swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

void rotateRightReversal(std::vector<int>& arr, int d) {
    int n = arr.size();
    if (n == 0 || d % n == 0) return;
    d = d % n; // Ensure d is within array bounds

    // For right rotation by d, we effectively want to rotate left by (N - d) positions
    // This translates to:
    // 1. Reverse the entire array
    // 2. Reverse first 'd' elements (which are now the last 'd' of original array)
    // 3. Reverse remaining 'N-d' elements (which are now the first 'N-d' of original array)
    // OR, applying the standard three reversals:
    // Reverse [0...n-d-1]
    // Reverse [n-d...n-1]
    // Reverse [0...n-1]

    // Let's use the explicit right rotation steps:
    // Step 1: Reverse the first N-d elements
    reverseArray(arr, 0, n - d - 1);

    // Step 2: Reverse the last d elements
    reverseArray(arr, n - d, n - 1);

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

int main() {
    // Step 1: Initialize an array and rotation amount
    std::vector<int> myArr = {1, 2, 3, 4, 5};
    int d = 2; // Number of positions to rotate right

    std::cout << "Original array: ";
    for (int x : myArr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Step 2: Perform right rotation
    rotateRightReversal(myArr, d);

    // Step 3: Print the rotated array
    std::cout << "Array after " << d << " right rotations: ";
    for (int x : myArr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

• Sample output:

Original array: 1 2 3 4 5 
Array after 2 right rotations: 4 5 1 2 3

 

• Stepwise explanation for clarity:

1. The reverseArray helper function is reused.
2. For a right rotation by d:
   • The elements from index 0 to N-d-1 are reversed.

• The elements from index N-d to N-1 (the last d elements) are reversed.
• Finally, the entire array from 0 to N-1 is reversed. This effectively rotates the array to the right.

Conclusion

Array rotation is a foundational concept with various practical applications. We explored three distinct methods for performing both left and right rotations in C++. While the temporary array method is intuitive, and the one-by-one rotation is simple for small rotations, the reversal algorithm stands out for its efficiency, offering an O(N) time complexity with O(1) auxiliary space, making it suitable for large datasets.

Summary

• Array Rotation: Shifting elements within an array by d positions (left or right).
• Left Rotation: Elements move to the left; first elements wrap to the end.
• Right Rotation: Elements move to the right; last elements wrap to the beginning.
• Temporary Array Method:
• Concept: Store first d elements, shift remaining, append stored.
• Complexity: O(N) time, O(d) space.
• One-by-One Rotation:
• Concept: Perform single rotations d times.
• Complexity: O(N\*d) time, O(1) space. Less efficient for large d.
• Reversal Algorithm:
• Concept: Three strategic reversals of array segments.
• Complexity: O(N) time, O(1) space. Generally the most efficient approach.