The O(n) Club: Remove Element — How to Clean Arrays Without Panic or Pain

The O(n) Club: Remove Element — How to Clean Arrays Without Panic or Pain

⚡ TL;DR

LeetCode #27 in plain English: Pretend you actually like your job. Walk through the array, overwrite each unwanted value (val) with better values, and return how many survivors remain. Don’t panic—don’t even look at the stuff after the new length. Here’s your Java starter pack:

int k = 0;
for (int i = 0; i < nums.length; i++) {
    if (nums[i] != val) {
        nums[k++] = nums[i];
    }
}
return k;

🧠 How Devs Usually Mess This Up

So the prompt says “remove all val in-place.” What does everyone do? They try to delete elements, but arrays in Java hold onto their size like a stubborn raccoon with a sandwich. Others spawn a shiny new ArrayList and copy the good stuff—congrats, you just failed ‘constant space.’ Or they sweat about the leftovers at the end of the array. Rule #1: nobody cares what’s after k. It’s algorithm limbo, my friend.

🔍 What’s Actually Going On

Imagine you’re sweeping a row of seats in a movie theater (the array). Every time you find a seat that’s not covered in pineapple pizza residue (not val), you move it forward in line. At the end of your cleaning, the first k seats are spotless. The rest can wait for the next apocalypse.

🛠️ PseudoCode

• Set up write pointer at zero:

  int k = 0;

  Ready to overwrite from up front.
• Scan the entire array:
  For every spot, check if it’s not that doomed value.
• If it’s good, overwrite at nums[k] and bump up k:

  if (nums[i] != val) nums[k++] = nums[i];

  It’s like a conveyor belt for keepers.
• Finish up:
  The first k slots are golden. Return k and call it a day.

💻 The Code

public int removeElement(int[] nums, int val) {
    int k = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != val) {
            nums[k++] = nums[i];
        }
    }
    return k;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Arrays Don’t Shrink: No remove(), no splice, no magical shrinking—stop trying.
• No New Arrays Allowed: They want in-place, not Amazon delivery.
• Order After ‘k’: Don’t waste brain cycles on it—it’s officially junk drawer territory.
• Duplicates? Negatives? Meh: Same rules: keep what’s not val, overwrite as needed.
• Big O for Humans: One loop (O(n)), zero extra gadgets (O(1)). If you make it O(n²), I’m mailing you more pineapple pizza.

🧠 Interviewer Brain-Tattoo

“It’s not about deleting stuff—it’s about deciding who still gets dinner after the array apocalypse.”