Left Rotate Array by K Places

Problem Statement

Given an integer array nums and a non-negative integer k, rotate the array to the left by k steps.

LeetCode:

• https://leetcode.com/problems/rotate-array/description/

Examples

Example 1:

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

Explanation: rotate 1 step to the left: [2, 3, 4, 5, 6, 1]
rotate 2 steps to the left: [3, 4, 5, 6, 1, 2]

Example 2:

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

Explanation: rotate 1 step to the left: [4, 1, 5, 3, -5, 3]
rotate 2 steps to the left: [1, 5, 3, -5, 3, 4]
rotate 3 steps to the left: [5, 3, -5, 3, 4, 1]
rotate 4 steps to the left: [3, -5, 3, 4, 1, 5]
rotate 5 steps to the left: [-5, 3, 4, 1, 5, 3]
rotate 6 steps to the left: [3, 4, 1, 5, 3, -5]
rotate 7 steps to the left: [4, 1, 5, 3, -5, 3]
rotate 8 steps to the left: [1, 5, 3, -5, 3, 4]

Different Approaches

1️⃣ Naive (Brute Force) Approach

Intuition:

We can rotate the array one element at a time. For each left rotation, shift each element of the array one position to the left, and move the first element to the end of the array.

Algorithm:

1. For each rotation (run this k times):
   • Save the first element in a temporary variable.
   • Shift every element in the array one position to the left.
   • Place the saved element at the last position.

Visualization:

arr : {1, 2, 3, 4, 5}, k = 2

First Iteration:

i = 0, k = 2
i < k
0 < 2
true
arr = {2, 3, 4, 5, 1}

i++

Second Iteration:

i = 1, k = 2
i < k
1 < 2
true
arr = {3, 4, 5, 1, 2}

i++

Loop Termination:

i = 2, k = 2
i < k
2 < 2
false

arr = {3, 4, 5, 1, 2}

return arr

Code:

#include <iostream>

void leftRotateByOne(int arr[], int n) {
    int temp = arr[0]; // Store the first element
    for (int i = 0; i < n - 1; i++) {
        arr[i] = arr[i + 1]; // Shift elements to the left
    }
    arr[n - 1] = temp; // Move the first element to the last position
}

void leftRotate(int arr[], int n, int k) {
    for (int i = 0; i < k; i++) {
        leftRotateByOne(arr, n); // Rotate the array by one k times
    }
}

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

    leftRotate(arr, n, k);

    std::cout << "Rotated array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n * k)
  • We perform k rotations, and each rotation shifts n elements. Therefore, the time complexity is O(n * k).
• Space Complexity: O(1)
  • Only a temporary variable is used to store the first element.

2️⃣ Using Auxiliary Array

Intuition:

To reduce the number of shifts, we can create a new array where the rotated elements are placed in their correct positions. This way, we avoid shifting elements multiple times.

Algorithm:

1. Create a temporary array of the same size.
2. Copy the elements starting from index k to the temporary array.
3. Copy the first k elements of the original array to the end of the temporary array.
4. Copy the temporary array back to the original array.

Visualization:

arr : {1, 2, 3, 4, 5}, k = 2

Temp Array:

Create a temp array of size n
temp = {0, 0, 0, 0, 0}

Copy elements from index k = 2 to end

Copy elements starting from index, k = 2 into temp array

arr = {1, 2, 3, 4, 5}, k = 2
temp = {3, 4, 5, 0, 0}

Copy the first k elements:

arr = {1, 2, 3, 4, 5}, k = 2
temp = {3, 4, 5, 1, 2}

Copy the temporary array back to the original array:

arr = {3, 4, 5, 1, 2}, k = 2
temp = {3, 4, 5, 1, 2}

Code:

#include <iostream>

void leftRotate(int arr[], int n, int k) {
    int temp[n]; // Temporary array

    // Copy elements starting from index k
    for (int i = 0; i < n - k; i++) {
        temp[i] = arr[i + k];
    }

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

    // Copy the temp array back to the original array
    for (int i = 0; i < n; i++) {
        arr[i] = temp[i];
    }
}

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

    leftRotate(arr, n, k);

    std::cout << "Rotated array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • We copy n elements twice (once to the temp array and once back to the original array).
• Space Complexity: O(n)
  • We use an extra array of size n to store the elements.

3️⃣ Optimal Approach (Reversal Algorithm)

Intuition:

The optimal solution is based on the reversal technique, which uses in-place rotations by reversing parts of the array. The idea is:

1. Reverse the first k elements.
2. Reverse the remaining n - k elements.
3. Reverse the entire array.

Algorithm:

1. Reverse the first k elements.
2. Reverse the last n - k elements.
3. Reverse the entire array.

Visualization:

arr = {1, 2, 3, 4, 5}, k = 2

Reverse the first k elements:

arr = {2, 1, 3, 4, 5}

Reverse the remaining n - k elements:

arr = {2, 1, 5, 4, 3}

Reverse the entire array:

arr = {3, 4, 5, 1, 2}

Code:

#include <iostream>
#include <algorithm> // For std::reverse

// Function to reverse a section of the array
void reverse(int arr[], int start, int end) {
    while (start < end) {
        std::swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

// Function to left rotate the array by k places using the reversal technique
void leftRotate(int arr[], int n, int k) {
    k = k % n; // Handle if k is greater than the size of the array

    // Step 1: Reverse the first k elements
    reverse(arr, 0, k - 1);

    // Step 2: Reverse the remaining n-k elements
    reverse(arr, k, n - 1);

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

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

    leftRotate(arr, n, k);

    std::cout << "Rotated array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • We perform three reversals, each taking O(n) time.
• Space Complexity: O(1)
  • The array is rotated in place, so no extra space is needed.