Rotate Array - The Elegant Three-Reversals Method

Introduction:

Today, we're tackling "Rotate Array" (LeetCode #189), a classic problem that's a brilliant example of in-place array manipulation.

We're tasked with rotating an array to the right by k steps. While there are several ways to approach this, we'll dive into an optimal and highly clever method known as the three-reversals technique that performs the rotation efficiently without using extra space. Let's master this array transformation!

---

Understanding the Problem:

You are given an integer array nums and a non-negative integer k. Our goal is to rotate the array nums to the right by k steps. This means elements from the end of the array move to the beginning.

Important Note on k: The value of k can be larger than the length of the array (n). For example, rotating an array of length 7 by 7 steps results in the original array. Rotating by 8 steps is equivalent to rotating by 1 step. This implies we should always work with k % n to find the effective number of rotations.

Example 1:

• Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3

• Output: [5, 6, 7, 1, 2, 3, 4]

  • Step-by-step rotation:

    • rotate 1 step to the right: [7, 1, 2, 3, 4, 5, 6]

    • rotate 2 steps to the right: [6, 7, 1, 2, 3, 4, 5]

    • rotate 3 steps to the right: [5, 6, 7, 1, 2, 3, 4]

Example 2:

• Input: nums = [-1, -100, 3, 99], k = 2

• Output: [3, 99, -1, -100]

  • Step-by-step rotation:

    • rotate 1 step to the right: [99, -1, -100, 3]

    • rotate 2 steps to the right: [3, 99, -1, -100]

---

My Thought Process & Approach (The Three-Reversals Method):

A naive approach might involve creating a new array, copying the last k elements to the beginning, and then the first n-k elements after them. This works but uses O(N) extra space. Another naive approach is to shift elements one by one, k times. This leads to O(N * K) time complexity, which is too slow if k is large.

The optimal solution, which performs the rotation in-place (O(1) additional space) and in O(N) time, uses a clever trick involving three reversals. Let's break down the logic:

The Intuition Behind Three Reversals:

Imagine you have two parts of the array:

• Part 1: The elements that will end up at the beginning of the rotated array (the last k elements of the original array).

• Part 2: The elements that will end up at the end of the rotated array (the first n-k elements of the original array).

Let's say our array is [A, B, C, D, E, F, G] and k=3. The last k=3 elements are [E, F, G]. The first n-k=4 elements are [A, B, C, D]. We want to transform [A, B, C, D | E, F, G] into [E, F, G | A, B, C, D].

Here's how the three reversals achieve this:

1. Step 1: Normalize k (Handle k > n)

   • Since rotating n times brings the array back to its original state, we only care about k % n.

   • k = k % n;

2. Step 2: Reverse the Entire Array.

   • This puts the elements that should be at the beginning of the rotated array (E, F, G) at the actual beginning, but in reverse order (G, F, E). It also puts A, B, C, D at the end, also in reverse.

   • Original: [A, B, C, D, E, F, G]

   • After full reverse: [G, F, E, D, C, B, A]

3. Step 3: Reverse the First k Elements.

   • Now, the k elements that should be at the front of the final array are actually at the front, but still reversed. Reversing them puts them in their correct order.

   • Current: [G, F, E | D, C, B, A] (where | denotes separation after k elements)

   • Reverse [G, F, E]: [E, F, G | D, C, B, A]

4. Step 4: Reverse the Remaining n-k Elements.

   • The elements that belong at the end of the final rotated array (A, B, C, D) are currently at the end, but also reversed (D, C, B, A). Reversing this second segment puts them in their correct final order.

   • Current: [E, F, G | D, C, B, A]

   • Reverse [D, C, B, A]: [E, F, G | A, B, C, D]

And just like that, the array is rotated right by k steps, perfectly in place!

Helper reverse Function: A simple two-pointer helper function can be used to reverse a segment of an array: one pointer from the left, one from the right, swap elements, and move pointers inwards until they cross.

---

Java Code Implementation:

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
         k = k%n;
        nums = reverse(nums,0,n-1);
        nums = reverse(nums,0,k-1);
        nums = reverse(nums,k,n-1);
        for(int i =0;i<n;i++){
            System.out.print(nums[i]+" ");
        }
    }
    public int[] reverse(int[] A, int l, int r){
        int temp = 0;
        while(l<r){
            temp = A[l];
            A[l]=A[r];
            A[r] = temp;
            l++;r--;
        }
        return A;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(N)

  • The reverse helper function iterates through roughly half of the elements in the segment it's reversing. Since we call reverse three times on parts of the array (entire array, first k elements, remaining n-k elements), each element in the array is effectively visited and swapped a constant number of times.

  • Therefore, the total time complexity is linear, O(N).

• Space Complexity: O(1)

  • The entire operation is performed directly on the input nums array.

  • Only a few constant-space variables (n, k, temp, l, r) are used.

  • No auxiliary data structures are created whose size depends on the input N.

  • This makes it a highly space-efficient in-place solution.