The O(n) Club: Move Zeroes — In-Place, In-Order, In-Interview Panic

The O(n) Club: Move Zeroes — In-Place, In-Order, In-Interview Panic

⚡ TL;DR

Move all zeroes to the end of your array—don’t use extra space, don’t start cheating, and keep everything else exactly where it was. Java makes this almost too easy to believe:

// Java one-liner-ish
int insert = 0;
for (int n : nums) if (n != 0) nums[insert++] = n;
while (insert < nums.length) nums[insert++] = 0;

🧠 How Devs Usually Mess This Up

Look, it happens. You see the word “in-place” and think, “Ah! Time for a brand-new array.” But your interviewer sees this and starts sobbing quietly. Copying non-zeroes to a fresh array is not in place—it’s in peril. Same goes for sorting—sure, the zeros all gather at the end, but so do your hopes of passing the interview, since nothing else stays in order. Swapping on every zero? Enjoy that write-amplified hard drive funeral.

🔍 What’s Actually Going On

Forget arrays: imagine you’re a bouncer at the world’s most boring nightclub. Everyone with a number gets in line. All the zeros are folks with fake IDs—they need to be sent to the end, but you’ve got to keep the rest of the crowd in their exact order. Best move? For each real guest (non-zero), step them up to the front as soon as you spot them, no skipping, no trampling. Once everyone legit is through, the rest of the line is zeros—perfectly preserved chaos.

🛠️ PseudoCode

• Get your write pointer ready: Set insert = 0, so you know where to stuff the next non-zero.
• Compact non-zeroes: For each number in the array:

  if (n != 0)
      nums[insert++] = n;

  Every non-zero takes its next seat; insert moves up like a snobby maître d’.

• Zero-fill the leftovers: For all spots after insert:

  while (insert < nums.length)
      nums[insert++] = 0;

  It’s like rerolling the empty tables after brunch.

💻 The Code

public void moveZeroes(int[] nums) {
    int insert = 0;
    // First, cram all non-zeroes to the front
    for (int n : nums) {
        if (n != 0) {
            nums[insert++] = n;
        }
    }
    // Fill the rest with zeros
    while (insert < nums.length) {
        nums[insert++] = 0;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Double Trouble: Don’t double-swap or shuffle every zero forward. It’s legal…but wasteful and just sad for your hardware.
• Order-obliterating Moves: Sorting or popping things from the middle won’t keep non-zero order. That’s an instant “nope” in interviews.
• Side-array Shenanigans: Using another array breaks the spirit of “in-place.” In interviews, it’s not just bad style—it’s grounds for gentle but soul-crushing rejection.
• Edge Case Game: Watch out for arrays that are all zero, all non-zero, or (bonus round!) empty.
• Runtime Story: You’re doing two passes, O(n) time. But your extra space? Just one or two variables. That’s even leaner than your coffee budget this month.

🧠 Interviewer Brain-Tattoo

If you can’t do it in-place, just remember: your tech lead will notice faster than your parents found your browser history.