Array Rotation in Java

This program demonstrates how to rotate an array by k positions to the right using Java.

Program Explanation

The goal is to shift all elements of the array to the right by k positions. For example, given the array [1, 2, 3, 4, 5] and k = 2, the output should be [4, 5, 1, 2, 3].

Steps Involved

1. Normalize the value of k to ensure it is within the bounds of the array length.
2. Reverse the entire array.
3. Reverse the first k elements.
4. Reverse the remaining n - k elements.

This approach ensures an efficient in-place rotation with a time complexity of O(n).

Java Code

public class ArrayRotation {
    
    // Function to rotate the array by k positions
    public static void rotate(int[] arr, int k) {
        int n = arr.length;
        // Normalize k to ensure it's within the bounds of the array length
        k = k % n;
        
        // Reverse the entire array
        reverse(arr, 0, n - 1);
        // Reverse the first k elements
        reverse(arr, 0, k - 1);
        // Reverse the remaining n - k elements
        reverse(arr, k, n - 1);
    }
    
    // Helper function to reverse a portion of the array
    private 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--;
        }
    }

    // Main function to test the array rotation
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;
        
        System.out.println("Original Array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        
        rotate(arr, k);
        
        System.out.println("\nArray after rotating by " + k + " positions: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
    

Code Explanation

The rotate function performs the array rotation in three steps:

• First, it normalizes the value of k using the modulus operator to handle cases where k is greater than the array length.
• It then reverses the entire array using the reverse helper function.
• Next, it reverses the first k elements.
• Finally, it reverses the remaining n - k elements.

The reverse function takes in the array and the start and end indices, swapping elements until the subarray is reversed.

The main function demonstrates the usage of the rotate function by rotating an example array {1, 2, 3, 4, 5} by 2 positions and printing the results before and after rotation.