The O(n) Club: Rotate Array: The Triple Reverse Shuffle You Secretly Hate

The O(n) Club: Rotate Array—The Triple Reverse Shuffle You Secretly Hate

⚡ TL;DR

Rotate your array to the right by k steps. Don’t copy arrays, don’t waste memory. Worship the triple-reverse method—it’s in-place and, shockingly, simple.

// Quick & punchy Java
void rotate(int[] nums, int k) {
    k = k % nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}
 void reverse(int[] nums, int left, int right) {
    while (left < right) {
        int temp = nums[left];
        nums[left++] = nums[right];
        nums[right--] = temp;
    }
}

🧠 How Devs Usually Mess This Up

Most devs, frantic on a whiteboard, grab a new array and start copying elements one by one. “Did I use extra O(n) space? Shh, maybe the interviewer didn’t see!” Others debug their spaghetti index math while silently questioning their career choices. Biggest party fouls:

• Copying everything to another array—memory leak in disguise.
• Nesting loops and making the CPU cry O(n²) tears.
• Rotating left instead of right (because who actually reads the problem?).
• Forgetting k = k % n: Congratulations, your rotations are now avant-garde.

🔍 What’s Actually Going On

Imagine your array as party guests in line for pizza. The last k folks get impatient, cut to the front, and the rest shuffle back. You could pass around nametags (allocating a new array), but it’s faster to run one epic conga line: reverse the whole gang, then the new front group, then the newly demoted back half. Three flips and everyone is exactly where they belong—no extra pizza boxes (memory) needed.

🛠️ PseudoCode

• Get sane k: k = k % n; // So 10 rotations in a 5-item array becomes just 0.
• Reverse the whole array:

  reverse(nums, 0, n - 1);

  Flip everyone head to toe.
• Reverse first k:

  reverse(nums, 0, k - 1);

  Undo the chaos for the shiny new front.
• Reverse the rest:

  reverse(nums, k, n - 1);

  Put the rest back in order (they’re not bitter, really).

Bonus: reverse just swaps from ends toward the center. Like fixing your hair in the mirror, but for arrays.

💻 The Code

public class RotateArray {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
     private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
     // Example:
    // int[] nums = {1,2,3,4,5,6,7};
    // new RotateArray().rotate(nums, 3);
    // nums is now [5,6,7,1,2,3,4]
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge case: k == 0 or k == n? Why are you rotating at all?
• Empty or one-element array: Please, go get some coffee instead.
• Missing the k % n step: Rotations go berserk beyond array’s length and make code reviewers sigh.
• One-liner reverses: Unless you’re a code golf wizard, split it out so you don’t reverse yourself into a corner.
• Time: Every element is touched thrice but it’s still O(n). Space: O(1), unless you can’t resist an extra array (don’t).

🧠 Interviewer Brain-Tattoo

“Copy arrays and you’re holding the pizza backwards. Triple reverse it—the space police won’t knock, and you’ll actually enjoy the slices.” 🍕