Skip to main content

Array Rotation (Left/Right)

Problem Statement:​

  • Example:

✅ Left Rotate – Using Extra Space (Normal Method)​

void rotateArr(vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n;

    vector<int> temp(k); // Step 1: store first k elements

    for (int i = 0; i < k; i++) {
        temp[i] = arr[i];
    }

    // Step 2: shift remaining elements to the left
    for (int i = k; i < n; i++) {
        arr[i - k] = arr[i];
    }

    // Step 3: place stored k elements at the end
    for (int i = 0; i < k; i++) {
        arr[n - k + i] = temp[i];
    }
}

✅ Left Rotate – Using Reverse Function​

void rotateArr(vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n;

    // Reverse the first k elements
    reverse(arr.begin(), arr.begin() + k);

    // Reverse the remaining n - k elements
    reverse(arr.begin() + k, arr.end());

    // Reverse the whole array
    reverse(arr.begin(), arr.end());
}

✅ Right Rotate – Using Extra Space (Normal Method)​

void rotateToRight(int arr[], int n, int k) {
    if (n == 0) return;

    k = k % n;
    if (k > n) return;

    int temp[k];

    // Step 1: Store last k elements
    for (int i = n - k; i < n; i++) {
        temp[i - (n - k)] = arr[i];
    }

    // Step 2: Shift first n - k elements to the right
    for (int i = n - k - 1; i >= 0; i--) {
        arr[i + k] = arr[i];
    }

    // Step 3: Place temp[] elements at the start
    for (int i = 0; i < k; i++) {
        arr[i] = temp[i];
    }
}

✅ Right Rotate – Using Reverse Function​

void rotateRight(vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n;

    // Step 1: Reverse last k elements
    reverse(arr.begin() + (n - k), arr.end());

    // Step 2: Reverse first n - k elements
    reverse(arr.begin(), arr.begin() + (n - k));

    // Step 3: Reverse entire array
    reverse(arr.begin(), arr.end());
}

📝 How It Works​

Left Rotate (Normal):​

  • Save the first k elements into a temp array.
  • Shift the rest to the left.
  • Place saved elements at the end.

Left Rotate (Reverse):​

  • Reverse first k, then rest, then whole array.
  • Works due to reversal rotation logic.

Right Rotate (Normal):​

  • Save the last k elements.
  • Shift remaining elements to the right.
  • Place saved elements at the beginning.

Right Rotate (Reverse):​

  • Reverse last k, then the rest, then the entire array.

🧩 Key Formula​

Reverse Logic:​

  • To left rotate by k, reverse in this order:
    1. First k
    2. Remaining n-k
    3. Whole array
  • To right rotate by k, reverse:
    1. Last k
    2. First n-k
    3. Whole array

⏱️ Time & Space Complexity​

VersionTimeSpace
Left Rotate (Normal)O(N)O(K)
Left Rotate (Reverse)O(N)O(1)
Right Rotate (Normal)O(N)O(K)
Right Rotate (Reverse)O(N)O(1)

⚠️ Edge Cases​

  • k = 0 → No rotation
  • k >= n → Normalize with k % n
  • Empty array → No operation
  • k == n → Full rotation → same as original

🔁 Related Problems​

  • Rotate Array (Leetcode 189)
  • Reverse a portion of array
  • Rotate Matrix
  • Cyclically Rotate Linked List
💬

Discussion & Doubts