The O(n) Club: Shuffle the Array: When ‘Shuffle’ Means Bring a Spreadsheet to a Card Table

The O(n) Club: Shuffle the Array—When ‘Shuffle’ Means Bring a Spreadsheet to a Card Table

⚡ TL;DR

LeetCode 1470 calls it ‘shuffle’, but unless your sense of chaos involves alternating office chairs at a meeting table, it’s just a polite interleaving of two halves. All you need is a new array, a humble for-loop, and zero imagination:

// Input: nums = [x1, x2, ..., xn, y1, y2, ..., yn]
// Output:     [x1, y1, x2, y2, ..., xn, yn]
int[] shuffle(int[] nums, int n) {
    int[] res = new int[2 * n];
    for (int i = 0; i < n; i++) {
        res[2 * i] = nums[i];
        res[2 * i + 1] = nums[n + i];
    }
    return res;
}

🧠 How Devs Usually Mess This Up

Somewhere out there right now, a dev sees the word ‘shuffle’ and instantly imports java.util.Random, ready to dice up this array like a Vegas blackjack dealer. Stop. This problem is allergic to entropy. If you write code for LeetCode’s “random shuffle” problem instead (that’s #384, friend), you’re writing the sequel to the wrong movie. And don’t let index math mess up your alternating dance—your job is to waltz, not trip over zero-based counting.

🔍 What’s Actually Going On

Imagine two lines at a very dull amusement park: one full of Xs, one full of Ys. The gates open and an algorithmic usher says, “One X, now one Y… keep going until everyone’s inside.” No surprises, just a zipper merge smoother than rush-hour traffic. And that’s the whole joke: this ‘shuffle’ is less wild Las Vegas, more Sunday school craft hour—just tidy, alternate merging, not a hint of randomness.

🛠️ PseudoCode

• Create a result array with space for all elements (2n, because we’re not doing any party tricks).
• For each position i in [0, n-1]:
  • Copy nums[i] to position 2i of the result (this is your X guy stepping up).
  • Copy nums[n+i] to position 2i+1 of the result (here’s the Y, dutifully following).

  for (int i = 0; i < n; i++) {
      res[2 * i] = nums[i];
      res[2 * i + 1] = nums[n + i];
  }

• Once you’ve reached n, everyone’s seated; return the result array.

💻 The Code

public int[] shuffle(int[] nums, int n) {
    int[] res = new int[2 * n];
    for (int i = 0; i < n; i++) {
        res[2 * i] = nums[i];
        res[2 * i + 1] = nums[n + i];
    }
    return res;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• RNG? No thanks. If you’re even thinking about Random, put the mouse down.
• Indexing agony: Forgetting that nums[n + i] is the Y group? Enjoy that ArrayIndexOutOfBoundsException. Be off by one and your result array will look like modern art.
• In-place showing-off: Sure, you can do it with O(1) space if you like cryptic code and sadistic debugging sessions, but O(n) extra space is perfectly kosher here.
• Complexity confession: It’s all O(n) time and O(n) space. Would be suspicious if it wasn’t.

🧠 Interviewer Brain-Tattoo

“If you see the word ‘shuffle’ and instinctively call random(), remember: sometimes an interviewer just wants you to be boring and correct.”