Rotate an Array to the Right by K Positions

Here’s a detailed explanation of the Rotate Array algorithm, including two methods for implementing it, along with time and space complexity analysis. The implementations are provided in C/C++, Java, and Python without using standard libraries.

Problem Statement

Given an array arr of n elements and an integer d, rotate the array to the right by d positions.

Methods for Rotating an Array

Method 1: Reverse Algorithm

This method involves three main steps:

1. Reverse the entire array.

2. Reverse the first d elements.

3. Reverse the remaining n - d elements.

Time Complexity

• O(n), where n is the number of elements in the array.

Space Complexity

• O(1), as the rotation is done in place.

1. C/C++ Implementation

#include <stdio.h>

void reverse(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp; // Swap elements
        start++;
        end--;
    }
}

void rotate_array_reverse(int arr[], int n, int d) {
    d = d % n; // Handle cases where d >= n
    reverse(arr, 0, n - 1);  // Step 1: Reverse the entire array
    reverse(arr, 0, d - 1);  // Step 2: Reverse the first d elements
    reverse(arr, d, n - 1);  // Step 3: Reverse the remaining elements
}

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

    rotate_array_reverse(arr, n, d);

    // Print rotated array
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2. Java Implementation

public class RotateArray {

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

    public static void rotateArrayReverse(int[] arr, int d) {
        int n = arr.length;
        d = d % n; // Handle cases where d >= n
        reverse(arr, 0, n - 1);  // Step 1: Reverse the entire array
        reverse(arr, 0, d - 1);  // Step 2: Reverse the first d elements
        reverse(arr, d, n - 1);  // Step 3: Reverse the remaining elements
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int d = 2;

        rotateArrayReverse(arr, d);

        // Print rotated array
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. Python Implementation

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

def rotate_array_reverse(arr, d):
    n = len(arr)
    d = d % n  # Handle cases where d >= n
    reverse(arr, 0, n - 1)  # Step 1: Reverse the entire array
    reverse(arr, 0, d - 1)  # Step 2: Reverse the first d elements
    reverse(arr, d, n - 1)  # Step 3: Reverse the remaining elements

# Example usage
arr = [1, 2, 3, 4, 5]
d = 2
rotate_array_reverse(arr, d)

# Print rotated array
print(arr)  # Output: [4, 5, 1, 2, 3]

Method 2: Using Extra Space

This method creates a new array to store the rotated elements:

1. Create a new array.

2. Copy elements to the new array based on the new positions after rotation.

3. Copy back to the original array.

Time Complexity

• O(n), where n is the number of elements in the array.

Space Complexity

• O(n), for the auxiliary array.

1. C/C++ Implementation

#include <stdio.h>
void rotate_array_extra_space(int arr[], int n, int d) {
    d = d % n; // Handle cases where d >= n
    int temp[n]; // Create a temporary array

    // Place elements in new positions
    for (int i = 0; i < n; i++) {
        int new_position = (i + d) % n;
        temp[new_position] = arr[i];
    }

    // Copy 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 d = 2;

    rotate_array_extra_space(arr, n, d);

    // Print rotated array
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2. Java Implementation

public class RotateArray {
    public static void rotateArrayExtraSpace(int[] arr, int d) {
        int n = arr.length;
        d = d % n; // Handle cases where d >= n
        int[] temp = new int[n]; // Create a temporary array

        // Place elements in new positions
        for (int i = 0; i < n; i++) {
            int new_position = (i + d) % n;
            temp[new_position] = arr[i];
        }

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

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int d = 2;

        rotateArrayExtraSpace(arr, d);

        // Print rotated array
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. Python Implementation

def rotate_array_extra_space(arr, d):
    n = len(arr)
    d = d % n  # Handle cases where d >= n
    temp = [0] * n  # Create a temporary array

    # Place elements in new positions
    for i in range(n):
        new_position = (i + d) % n
        temp[new_position] = arr[i]

    # Copy back to the original array
    for i in range(n):
        arr[i] = temp[i]

# Example usage
arr = [1, 2, 3, 4, 5]
d = 2
rotate_array_extra_space(arr, d)

# Print rotated array
print(arr)  # Output: [4, 5, 1, 2, 3]

Summary of Both Methods

Both methods are effective for rotating an array, but the first method is more space-efficient, while the second method is simpler and more intuitive. Choose the method that best fits your needs based on the constraints of your problem.