Array Rotation

Problem Statement

Write a Java program that rotates an array of integers by k positions to the left. The rotation should shift each element k positions left, with elements at the beginning wrapping around to the end of the array. The program should modify the array in-place and test the implementation with different values of k and array sizes, including edge cases like empty arrays, single-element arrays, and k larger than the array length. You can visualize this as rotating a circular table of numbered plates k positions counterclockwise, so the first k plates move to the end while the rest shift forward.

Input: An array of integers and a non-negative integer k (e.g., arr = [1, 2, 3, 4, 5], k = 2). Output: The array modified in-place to reflect the left rotation by k positions (e.g., [3, 4, 5, 1, 2]). Constraints:

• The array length is between 0 and 10^5.
• Elements are integers between -10^9 and 10^9.
• k is a non-negative integer (0 ≤ k ≤ 10^9).
• The array may be empty. Example:
• Input: arr = [1, 2, 3, 4, 5], k = 2
• Output: [3, 4, 5, 1, 2]
• Explanation: Rotating [1, 2, 3, 4, 5] left by 2 positions moves 1 and 2 to the end.
• Input: arr = [1, 2, 3], k = 4
• Output: [3, 1, 2]
• Explanation: Rotating by k = 4 is equivalent to k = 1 (since 4 % 3 = 1).

Pseudocode

FUNCTION rotateArray(arr, k)
    IF arr is null OR length of arr <= 1 THEN
        RETURN
    ENDIF
    SET n to length of arr
    SET k to k modulo n
    IF k equals 0 THEN
        RETURN
    ENDIF
    CALL reverseArray(arr, 0, k - 1)
    CALL reverseArray(arr, k, n - 1)
    CALL reverseArray(arr, 0, n - 1)
ENDFUNCTION

FUNCTION reverseArray(arr, start, end)
    WHILE start < end
        SET temp to arr[start]
        SET arr[start] to arr[end]
        SET arr[end] to temp
        INCREMENT start
        DECREMENT end
    ENDWHILE
ENDFUNCTION

FUNCTION main()
    SET testCases to array of tuples (arr, k)
    FOR each (arr, k) in testCases
        CALL rotateArray(arr, k)
        PRINT arr
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Check if the input array is null or has 0 or 1 element. If so, return, as no rotation is needed.
2. Compute the effective rotation value: k = k % n, where n is the array length, to handle cases where k exceeds n.
3. If k equals 0 after modulo, return, as no rotation is needed.
4. Use the reversal algorithm to rotate the array in-place: a. Reverse the first k elements (indices 0 to k-1). b. Reverse the remaining elements (indices k to n-1). c. Reverse the entire array (indices 0 to n-1).
5. The reverseArray helper function swaps elements from start to end using a temporary variable.
6. In the main method, create test cases with different array sizes and k values, call rotateArray, and print the results.

Java Implementation

public class ArrayRotation {
    // Rotates array left by k positions in-place
    public void rotateArray(int[] arr, int k) {
        // Check for null or single-element/empty array
        if (arr == null || arr.length <= 1) {
            return;
        }
        // Normalize k to handle cases where k > array length
        int n = arr.length;
        k = k % n;
        if (k == 0) {
            return;
        }
        // Perform three reversals
        reverseArray(arr, 0, k - 1);
        reverseArray(arr, k, n - 1);
        reverseArray(arr, 0, n - 1);
    }

    // Helper function to reverse array segment from start to end
    private void reverseArray(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }

    // Main method to test rotateArray with various inputs
    public static void main(String[] args) {
        ArrayRotation rotator = new ArrayRotation();

        // Test case 1: Normal array, k = 2
        int[] arr1 = {1, 2, 3, 4, 5};
        System.out.print("Test case 1 before: ");
        printArray(arr1);
        rotator.rotateArray(arr1, 2);
        System.out.print("Test case 1 after: ");
        printArray(arr1);

        // Test case 2: k > array length
        int[] arr2 = {1, 2, 3};
        System.out.print("Test case 2 before: ");
        printArray(arr2);
        rotator.rotateArray(arr2, 4);
        System.out.print("Test case 2 after: ");
        printArray(arr2);

        // Test case 3: Empty array
        int[] arr3 = {};
        System.out.print("Test case 3 before: ");
        printArray(arr3);
        rotator.rotateArray(arr3, 3);
        System.out.print("Test case 3 after: ");
        printArray(arr3);

        // Test case 4: Single-element array
        int[] arr4 = {7};
        System.out.print("Test case 4 before: ");
        printArray(arr4);
        rotator.rotateArray(arr4, 2);
        System.out.print("Test case 4 after: ");
        printArray(arr4);

        // Test case 5: k = 0
        int[] arr5 = {1, 2, 3, 4};
        System.out.print("Test case 5 before: ");
        printArray(arr5);
        rotator.rotateArray(arr5, 0);
        System.out.print("Test case 5 after: ");
        printArray(arr5);
    }

    // Helper method to print array
    private static void printArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            System.out.println("[]");
            return;
        }
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}

Output

Running the main method produces:

Test case 1 before: [1, 2, 3, 4, 5]
Test case 1 after: [3, 4, 5, 1, 2]
Test case 2 before: [1, 2, 3]
Test case 2 after: [3, 1, 2]
Test case 3 before: []
Test case 3 after: []
Test case 4 before: [7]
Test case 4 after: [7]
Test case 5 before: [1, 2, 3, 4]
Test case 5 after: [1, 2, 3, 4]

Explanation:

• Test case 1: Rotates [1, 2, 3, 4, 5] left by 2, resulting in [3, 4, 5, 1, 2].
• Test case 2: Rotates [1, 2, 3] by k = 4, equivalent to k = 1 (4 % 3), resulting in [3, 1, 2].
• Test case 3: Empty array remains [].
• Test case 4: Single-element array [7] remains unchanged.
• Test case 5: k = 0 leaves [1, 2, 3, 4] unchanged.

How It Works

• Step 1: The rotateArray method checks if the array is null or has 0 or 1 element. For [1, 2, 3, 4, 5], k = 2, it proceeds.
• Step 2: Normalize k: n = 5, k = 2 % 5 = 2.
• Step 3: Perform three reversals:
  • Reverse indices 0 to 1: [2, 1, 3, 4, 5].
  • Reverse indices 2 to 4: [2, 1, 5, 4, 3].
  • Reverse entire array: [3, 4, 5, 1, 2].
• Example Trace: For [1, 2, 3, 4, 5], k = 2, reverses [1, 2] to [2, 1], [3, 4, 5] to [5, 4, 3], then [2, 1, 5, 4, 3] to [3, 4, 5, 1, 2].
• Main Method: Tests the method with various cases: normal rotation, k > n, empty array, single-element array, and k = 0.
• In-Place Property: The algorithm uses O(1) extra space by performing swaps via the reverseArray helper.

Complexity Analysis Table

Note:

• n is the size of the input array.
• Time complexity: O(n), as the algorithm performs three reversals, each taking O(n/2), O(n-k), and O(n) respectively, totaling O(n).
• Space complexity: O(1), as only a few temporary variables are used for swapping.
• Best, average, and worst cases are O(n).

✅ Tip: Normalize k using modulo to handle large k values efficiently. Test with edge cases like k = 0, k > n, and empty arrays to ensure robustness.

⚠ Warning: Ensure the input array is not null to avoid NullPointerException. Verify index bounds in the reverse function to prevent ArrayIndexOutOfBoundsException.