Rotating an array to the right by K steps means shifting every element forward by K places, with elements at the end wrapping back around to the beginning. For example, rotating [1, 2, 3, 4, 5, 6, 7] by 3 positions gives [5, 6, 7, 1, 2, 3, 4].

To rotate an array in-place (without creating a copy of the array), we use an elegant math shortcut called the Triple-Reverse trick. Let's see how it works using a simple lazy susan turntable analogy.

Illustration of the steps to rotate an array using the triple reverse trick
Real-World Analogy: The Table Cards and the lazy susan

Imagine you have 7 cards labeled [1, 2, 3, 4] (blue cards) and [5, 6, 7] (green cards) sitting in a row on a turntable. You want to shift them all 3 places to the right so the green cards end up in front:

Target: [5, 6, 7, 1, 2, 3, 4]

Instead of lifting cards and shifting them one by one, you perform three simple flips:

  • Flip 1 (Reverse All): Spin the entire turntable. The cards are now: [7, 6, 5, 4, 3, 2, 1].
  • Flip 2 (Reverse First K): Reverse just the first 3 cards (the green ones): [7, 6, 5] becomes [5, 6, 7]. The cards are now: [5, 6, 7, 4, 3, 2, 1].
  • Flip 3 (Reverse Remaining): Reverse the remaining 4 cards (the blue ones): [4, 3, 2, 1] becomes [1, 2, 3, 4]. The cards are now: [5, 6, 7, 1, 2, 3, 4]!

Walkthrough of the Rotation Scenario

Let's trace how the program executes step-by-step from the entry point of the main method:

Step 1: Declaring the input array

The program declares the target array and the shifting factor:

int[] arr = {1, 2, 3, 4, 5, 6, 7};
int k = 3;
Step 2: Processing the Triple-Reverse

The program triggers the swaps in order:

  • First: Reverses the whole array (indices 0 to 6): {7, 6, 5, 4, 3, 2, 1}.
  • Second: Reverses the first 3 elements (indices 0 to 2): {5, 6, 7, 4, 3, 2, 1}.
  • Third: Reverses the remaining 4 elements (indices 3 to 6): {5, 6, 7, 1, 2, 3, 4}.

Java Implementation

Below is the complete Java code demonstrating in-place array rotation:

package io.practise.accolite;
 
import java.util.Arrays;
 
public class RotatingArrayKTime {
 
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;
 
        rotate(arr, k);
 
        System.out.println(Arrays.toString(arr)); // Outputs: [5, 6, 7, 1, 2, 3, 4]
    }
 
    public static void rotate(int[] nums, int k) {
        k = k % nums.length; // handles cases where k is larger than the array length
        reverse(nums, 0, nums.length - 1); // Step 1: reverse all
        reverse(nums, 0, k - 1);           // Step 2: reverse first K
        reverse(nums, k, nums.length - 1); // Step 3: reverse the rest
    }
 
    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Conclusion

The Triple-Reverse algorithm rotates arrays in O(N) time complexity and O(1) space complexity. It is the most memory-efficient way to shift collections of data without needing temporary placeholder arrays!