🔄 Rotate an Array by k Positions in DSA

🌟 Introduction

Array rotation is a common problem in Data Structures and Algorithms (DSA), often asked in coding interviews. The task is simple: given an array, shift its elements by k positions either to the left or to the right.

For example

👉 Input: arr = [1, 2, 3, 4, 5], k = 2
👉 Left Rotation: [3, 4, 5, 1, 2]
👉 Right Rotation: [4, 5, 1, 2, 3]

This problem helps you understand array manipulation, modular arithmetic, and in-place algorithms.

🧩 Types of Array Rotation

There are mainly two types of rotation:

1. Left Rotation: Each element is shifted to the left by one, and the first element goes to the end.

   • Example: [1, 2, 3, 4, 5] → [2, 3, 4, 5, 1]

2. Right Rotation: Each element is shifted to the right by one, and the last element comes to the front.

   • Example: [1, 2, 3, 4, 5] → [5, 1, 2, 3, 4]

⚙️ Approaches to Solve the Problem

1️⃣ Naive Approach (Using Extra Space)

• Store elements of the array in a temporary array after rotation.

• Copy them back to the original array.

⏱️ Time Complexity: O(n)
💾 Space Complexity: O(n)

2️⃣ Juggling Algorithm (Efficient)

• Based on finding GCD (Greatest Common Divisor) of n and k.

• Rotate elements in sets determined by GCD.

⏱️ Time Complexity: O(n)
💾 Space Complexity: O(1)

3️⃣ Reversal Algorithm (Most Popular)

For left rotation by k:

1. Reverse first k elements.

2. Reverse remaining n-k elements.

3. Reverse the whole array.

For right rotation by k:

1. Reverse last k elements.

2. Reverse first n-k elements.

3. Reverse the whole array.

⏱️ Time Complexity: O(n)
💾 Space Complexity: O(1)

💻 Code Implementations

✅ C++ Code

#include <bits/stdc++.h>using namespace std;

void reverseArray(vector<int>& arr, int start, int end) {
    while (start < end) {
        swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

void leftRotate(vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n;
    reverseArray(arr, 0, k-1);
    reverseArray(arr, k, n-1);
    reverseArray(arr, 0, n-1);
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int k = 2;
    leftRotate(arr, k);
    for (int x : arr) cout << x << " ";
}

✅ Java Code

import java.util.*;

public class RotateArray {
    static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }

    static void leftRotate(int[] arr, int k) {
        int n = arr.length;
        k = k % n;
        reverse(arr, 0, k-1);
        reverse(arr, k, n-1);
        reverse(arr, 0, n-1);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;
        leftRotate(arr, k);
        System.out.println(Arrays.toString(arr));
    }
}

✅ Python Code

def reverse(arr, start, end):
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1

def left_rotate(arr, k):
    n = len(arr)
    k = k % n
    reverse(arr, 0, k-1)
    reverse(arr, k, n-1)
    reverse(arr, 0, n-1)
    return arr

arr = [1, 2, 3, 4, 5]
k = 2print(left_rotate(arr, k))

📊 Time & Space Complexity

Approach	Time Complexity	Space Complexity
Naive (Extra Space)	O(n)	O(n)
Juggling Algorithm	O(n)	O(1)
Reversal Algorithm	O(n)	O(1)

🎯 Conclusion

Array rotation is a fundamental problem that strengthens your basics in DSA. Among different methods, the Reversal Algorithm is the most efficient and widely used in interviews.