Understanding Rotate Array in Java

Introduction & Problem Explanation

The Rotate Array problem asks us to shift the elements of an array to the right by k steps, where k is a non-negative integer.

For example, if we have the array [1, 2, 3, 4, 5, 6, 7] and we want to rotate it by k = 3, the output should be [5, 6, 7, 1, 2, 3, 4]. The primary challenge is performing this rotation efficiently in-place with O(1) auxiliary space, as creating copies of large arrays is not memory-efficient.

The Algorithmic Approach

1. The Naive Approach (O(n * k) Time, O(1) Space)

We can shift the elements of the array to the right by one position, k times. While this is in-place, the time complexity is O(n * k). If k is large, this is extremely slow.

2. Extra Array Approach (O(n) Time, O(n) Space)

We can copy the elements to a temporary array at their new calculated positions: newPosition = (currentPosition + k) % size. After that, we copy it back. This takes linear time but uses O(n) extra memory.

3. The Reversal Algorithm (O(n) Time, O(1) Space)

This is the most optimized approach. By reversing segments of the array, we can achieve rotation in-place in linear time. The steps are:

1. Perform modulo operation on k: k = k % size to handle cases where k is larger than the array length.
2. Reverse the entire array.
3. Reverse the first k elements.
4. Reverse the remaining n - k elements.

This achieves O(n) time complexity and O(1) space complexity.

Step-by-Step Execution Walkthrough

Let's trace the reversal rotation on the array nums = [1, 2, 3, 4, 5, 6, 7] with k = 3:

1. Step 1 (Normalize k): k = 3 % 7 = 3.
2. Step 2 (Reverse the entire array):
   • We call reverse(nums, 0, 6).
   • Pointers at index 0 and 6 swap values. Pointers move inwards and repeat.
   • Array changes: [1, 2, 3, 4, 5, 6, 7] → [7, 6, 5, 4, 3, 2, 1].
3. Step 3 (Reverse the first k elements):
   • We call reverse(nums, 0, k - 1) which is reverse(nums, 0, 2).
   • This reverses the subarray [7, 6, 5].
   • Array changes: [7, 6, 5, 4, 3, 2, 1] → [5, 6, 7, 4, 3, 2, 1].
4. Step 4 (Reverse the remaining elements):
   • We call reverse(nums, k, nums.length - 1) which is reverse(nums, 3, 6).
   • This reverses the subarray [4, 3, 2, 1].
   • Array changes: [5, 6, 7, 4, 3, 2, 1] → [5, 6, 7, 1, 2, 3, 4].
5. Step 5 (Completion): The rotation is complete. The resulting array is [5, 6, 7, 1, 2, 3, 4].

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• k %= nums.length;: Ensures we do not perform redundant full-circle rotations. For example, rotating an array of size 5 by 6 steps is equivalent to rotating it by 1 step.
• reverse(nums, 0, nums.length - 1);: Places all elements that need to end up at the front in the correct left half, although their internal order is inverted.
• reverse(nums, 0, k - 1); and reverse(nums, k, nums.length - 1);: Restore the original relative ordering of the two segments after the global reversal.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Arrays;

public class RotateArray {

    // Brute Force - O(n * k)
    public void rotateBrute(int[] nums, int k) {
        k %= nums.length;
        for (int i = 0; i < k; i++) {
            int last = nums[nums.length - 1];
            for (int j = nums.length - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = last;
        }
    }

    // Optimized - O(n) with reversal
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }

    public static void main(String[] args) {
        RotateArray solver = new RotateArray();
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;

        System.out.println("--- Rotate Array Demonstration ---");
        System.out.println("Input Array: " + Arrays.toString(nums));
        System.out.println("Rotate Right by: " + k);

        int[] testNums = nums.clone();
        System.out.println("\nExecuting Reversal-Based Rotation...");
        System.out.println("Step 1: Reverse entire array -> " + Arrays.toString(testNums));
        solver.reverse(testNums, 0, testNums.length - 1);
        System.out.println("  Result: " + Arrays.toString(testNums));
        
        System.out.println("Step 2: Reverse first k elements (0 to k-1) -> " + Arrays.toString(testNums));
        solver.reverse(testNums, 0, k - 1);
        System.out.println("  Result: " + Arrays.toString(testNums));
        
        System.out.println("Step 3: Reverse remaining elements (k to end) -> " + Arrays.toString(testNums));
        solver.reverse(testNums, k, testNums.length - 1);
        System.out.println("  Result: " + Arrays.toString(testNums));
    }
}

Conclusion

Solving the Rotate Array problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.