Rotate Array Problem Explained — 3 Approaches, Real Trade-offs

public class BruteForceRotation {

    /**
     * Rotates the array to the right by 'steps' positions.
     * Strategy: perform a single-step rotation exactly 'steps' times.
     * Time:  O(n * steps)  — we touch every element once per step
     * Space: O(1)          — only one extra variable to hold the displaced element
     */
    public static void rotateRight(int[] elements, int steps) {
        int length = elements.length;
        if (length == 0) return;

        // Reduce redundant full-cycle rotations.
        // e.g. rotating 5 elements by 7 is identical to rotating by 2.
        steps = steps % length;

        for (int round = 0; round < steps; round++) {
            // Save the element that will be displaced from the end
            int displaced = elements[length - 1];

            // Shift every element one position to the right
            for (int i = length - 1; i > 0; i--) {
                elements[i] = elements[i - 1]; // each element takes the value of its left neighbour
            }

            // The displaced tail element wraps around to the front
            elements[0] = displaced;
        }
    }

    public static void main(String[] args) {
        int[] schedule = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("Before rotation: " + java.util.Arrays.toString(schedule));

        rotateRight(schedule, 3);
        System.out.println("After rotating right by 3: " + java.util.Arrays.toString(schedule));

        // Edge case: k larger than array length
        int[] taskQueue = {10, 20, 30, 40, 50};
        System.out.println("\nBefore rotation: " + java.util.Arrays.toString(taskQueue));
        rotateRight(taskQueue, 7); // 7 % 5 = 2, so effectively 2 steps
        System.out.println("After rotating right by 7 (same as 2): " + java.util.Arrays.toString(taskQueue));
    }
}

public class ExtraArrayRotation {

    /**
     * Rotates the array to the right by 'steps' positions using a temporary buffer.
     * Time:  O(n) — single pass to place elements, single pass to copy back
     * Space: O(n) — we allocate a second array of equal size
     */
    public static void rotateRight(int[] elements, int steps) {
        int length = elements.length;
        if (length == 0) return;

        steps = steps % length; // guard against k >= n
        if (steps == 0) return;  // guard against no-op rotation

        int[] buffer = new int[length];

        // Place each element at its final destination in the buffer.
        // An element at index i in a right-rotation moves to (i + steps) % length.
        for (int i = 0; i < length; i++) {
            int destination = (i + steps) % length;
            buffer[destination] = elements[i];
        }

        // Copy the correctly-ordered buffer back into the original array
        // so the caller sees the result in-place.
        System.arraycopy(buffer, 0, elements, 0, length);
    }

    public static void main(String[] args) {
        int[] playlist = {"Song A", "Song B", "Song C", "Song D", "Song E"}; // conceptual
        int[] trackIds = {101, 102, 103, 104, 105};

        System.out.println("Playlist before shuffle-rotate: " + java.util.Arrays.toString(trackIds));
        rotateRight(trackIds, 2);
        System.out.println("Playlist after rotating right by 2: " + java.util.Arrays.toString(trackIds));

        // Verify the destination formula manually:
        // index 0 (101) -> (0+2)%5 = 2  ✓
        // index 1 (102) -> (1+2)%5 = 3  ✓
        // index 2 (103) -> (2+2)%5 = 4  ✓
        // index 3 (104) -> (3+2)%5 = 0  ✓ (wraps around)
        // index 4 (105) -> (4+2)%5 = 1  ✓ (wraps around)

        int[] sensors = {5, 10, 15, 20, 25, 30};
        System.out.println("\nSensor readings before: " + java.util.Arrays.toString(sensors));
        rotateRight(sensors, 6); // 6 % 6 = 0, no change expected
        System.out.println("After rotating by 6 (full cycle): " + java.util.Arrays.toString(sensors));
    }
}

public class ReversalTrickRotation {

    /**
     * Rotates the array to the right by 'steps' positions using three reversals.
     * Time:  O(n) — each element is touched at most twice across all three reversals
     * Space: O(1) — swaps happen in-place with a single temporary variable
     *
     * The three-step recipe:
     *   1. Reverse the ENTIRE array
     *   2. Reverse the FIRST k elements  (the future front section)
     *   3. Reverse the REMAINING n-k elements (the future back section)
     */
    public static void rotateRight(int[] elements, int steps) {
        int length = elements.length;
        if (length == 0) return;

        steps = steps % length;
        if (steps == 0) return;

        // Step 1: Flip the whole array
        // [1,2,3,4,5,6,7] with k=3 -> [7,6,5,4,3,2,1]
        reverse(elements, 0, length - 1);

        // Step 2: Reverse the first 'steps' elements
        // [7,6,5,4,3,2,1] -> [5,6,7,4,3,2,1]
        reverse(elements, 0, steps - 1);

        // Step 3: Reverse the remaining elements from index 'steps' to end
        // [5,6,7,4,3,2,1] -> [5,6,7,1,2,3,4]
        reverse(elements, steps, length - 1);
    }

    /**
     * Reverses a sub-section of the array between indices 'from' and 'to' inclusive.
     * Uses two-pointer swap — no extra array needed.
     */
    private static void reverse(int[] elements, int from, int to) {
        while (from < to) {
            int temp = elements[from];
            elements[from] = elements[to];
            elements[to] = temp;
            from++;
            to--;
        }
    }

    public static void main(String[] args) {
        // --- Example 1: Standard rotation ---
        int[] taskQueue = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("Original task queue:  " + java.util.Arrays.toString(taskQueue));
        rotateRight(taskQueue, 3);
        System.out.println("After right rotate k=3: " + java.util.Arrays.toString(taskQueue));

        // --- Example 2: k = 1 (shift by one, common in round-robin) ---
        int[] servers = {101, 102, 103, 104, 105};
        System.out.println("\nServer order before:  " + java.util.Arrays.toString(servers));
        rotateRight(servers, 1);
        System.out.println("After round-robin shift: " + java.util.Arrays.toString(servers));

        // --- Example 3: k > n (handled by modulo) ---
        int[] pixels = {255, 128, 64, 32, 16};
        System.out.println("\nPixel values before:  " + java.util.Arrays.toString(pixels));
        rotateRight(pixels, 12); // 12 % 5 = 2
        System.out.println("After rotate k=12 (effective k=2): " + java.util.Arrays.toString(pixels));
    }
}