The O(n) Club: Remove Duplicates from Sorted Array II—Twice Is Nice, Thrice Is Jail

The O(n) Club: Remove Duplicates from Sorted Array II—Twice Is Nice, Thrice Is Jail

⚡ TL;DR

Your sorted array needs some tough love: keep each value only twice, in-place, and ignore the rest like last week’s sprint retro. Best tool? A pointer that says who gets in and who waits outside:

// Java: allow each value twice, in-place
int i = 0;
for (int num : nums)
    if (i < 2 || num != nums[i - 2])
        nums[i++] = num;
return i;

🧠 How Devs Usually Mess This Up

There’s the LeetCode 26 confusion club—if you think this is “unique-or-bust,” look again! Here, duplicates are like coffee refills: two is fine, three is regrettable. The usual fails?

• Deep copy disaster: People create new arrays. Big no-no—the problem says “in-place.” Memory police, incoming.
• Mutant removal: You physically try to remove elements from arrays (with a fixed length!). That’s pain you don’t need.
• HashSet overkill: Sets are lovely for uniqueness, but that’s not our flavor of weird today. Each value can show up twice, so HashSet’s not just useless—it’ll fail the test cases, too.
• Thinking you must visually delete extra numbers? Nope. Just report the new length and ignore the junk past that index. Out of sight, out of mind (and scope).

🔍 What’s Actually Going On

Imagine a tiny, overworked nightclub bouncer (your index i) monitoring the door to Array Lounge. Each guest’s allowed in twice, but after that, it’s velvet-rope denial.

The guest list is sorted (because the programmer is civilized), so when the same name queues up for a third time, the bouncer just stares ahead, completely ignoring the beggar. Only the first two passes count—loop, check, let in if not already doubled up. That’s the two-pointer trick: one pointer loops, one writes legit entries up front.

🛠️ PseudoCode

• Set i = 0: i is your “open seat” marker for what’s allowed in.
• Loop through nums: For each num, do the following:

• if (i < 2)

  First two guests: Always let them in—no history, no drama.

• if (num != nums[i-2])

  Beyond that: Only allow num if it isn’t the same as both last two stored.
• If the check passes, write num at position i, and bump i by one. If not? They’re loitering outside the club forever.
• Once loop is done, i is the new guest list’s real length. Everyone past i is… not your problem.

💻 The Code

public class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int num : nums) {
            if (i < 2 || num != nums[i - 2]) {
                nums[i++] = num;
            }
        }
        return i;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Short arrays: Fewer than two elements? Don’t sweat it; everything is valid.
• All duplicates: Like four sevens in a row? Only two survive, rest go MIA.
• Attempting to ‘delete’ from arrays: Java’s arrays don’t shrink; just write up to i. Stop pretending Java arrays are ArrayLists, and you’ll sleep better.
• Runtime: O(n), because you only walk through once. Space? It’s O(1), unless you start daydreaming about new arrays (don’t).

🧠 Interviewer Brain-Tattoo

“If you reach for a HashSet, you might as well reach for your resume—this problem’s all about *counted* duplicates, not unique values.”