Left Rotate Array - C++ Solution

1. Introduction

In this blog post, we address a common problem in array manipulation: left-rotating an integer array by k positions. This task involves shifting the array elements to the left k times, wrapping around the array. The problem tests one's understanding of array indexing and rotation in C++.

Problem

Given an integer array nums, the task is to left-rotate the array by k positions. k is a positive integer, and rotations should be done in-place.

Examples:

- Input: nums[] = [1, 2, 3, 4, 5], k = 2

Output: [3, 4, 5, 1, 2]

- Input: nums[] = [1, 2, 3, 4, 5], k = 6

Output: [1, 2, 3, 4, 5]

2. Solution Steps

1. Normalize k to ensure it's within the array's length.

2. Reverse the entire array.

3. Reverse the first k elements.

4. Reverse the remaining elements.

5. The array is now left-rotated by k positions.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to reverse a part of the array
void reverseArray(vector<int>& nums, int start, int end) {
    while (start < end) {
        swap(nums[start], nums[end]);
        start++;
        end--;
    }
}

// Function to left-rotate the array by k positions
void leftRotateArray(vector<int>& nums, int k) {
    int n = nums.size();
    k %= n; // Normalize k

    // Reverse the entire array
    reverseArray(nums, 0, n - 1);
    // Reverse the first k elements
    reverseArray(nums, 0, k - 1);
    // Reverse the remaining elements
    reverseArray(nums, k, n - 1);
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    int k = 2;
    leftRotateArray(nums, k);

    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

Output:

3 4 5 1 2

Explanation:

The leftRotateArray function first normalizes k to ensure it falls within the array's length. It then reverses the entire array, which sets the stage for the left rotation. The first k elements are then reversed, followed by reversing the remaining elements. This sequence of reversals effectively performs a left rotation of the array by k positions, as shown in the output for the given example.