The O(n) Club: Remove Duplicates from Sorted Array—Why Is This Still an Interview Question?

The O(n) Club: Remove Duplicates from Sorted Array—Why Is This Still an Interview Question?

⚡ TL;DR

Your boss (or LeetCode, or that one smug interviewer) wants you to strip duplicates out of a sorted array in-place. No extra memory. No copy-paste arrays. The solution? Channel your inner two-pointer ninja:

// Java: Return the count of unique elements—in-place!
int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

🧠 How Devs Usually Mess This Up

First, panic and open Stack Overflow in sixteen tabs. Next, slap together a shiny ArrayList to hold uniques—so much for O(1) space! Or maybe you try to resize the array, forgetting Java arrays are about as flexible as a lead pipe. Sometimes people even ignore the sorted part and brute-force every combo. Congratulations, your solution is now sponsored by the OutOfMemoryError Fairy and the Ghost of N^2 Past.

🔍 What’s Actually Going On

Visualize a marching band, all sorted by height, but some kids show up twice. You get two batons: one points to the last unique bandmate, the other scouts ahead. Every time the scout finds someone new, you wave them into the next empty slot. No need to care about the trailing riff-raff—they’re outside the performance area (aka: ignore everything past the k returned). It’s an elegant O(n) space-saving dance.

🛠️ PseudoCode

• Let i = 0 (the last index with a unique value).
• Iterate j from 1 to end:
• If nums[j] != nums[i] (found a new unique):
  • Bump i++
  • nums[i] = nums[j]
• No match? Keep scanning. Duplicates can go eat static.
• Return i + 1—your “unique” count.

Why doesn’t everyone do this? Apparently reading the instructions is harder than O(n).

💻 The Code

public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Miss “sorted” and brute-force everything? Enjoy exponential runtime, legend.
• Using extra space for a separate array? Read the requirements again—slowly this time.
• Returning the wrong thing: Only the first k values matter. Whatever is past that in the array? Good luck, buddy.
• Empty array = return 0 and do not pass Go. Avoid NullPointerException speedruns.
• Time: O(n) (so you can impress managers with buzzwords). Space: O(1)—flex achieved.

🧠 Interviewer Brain-Tattoo

Remember: if your solution copies arrays, you just failed the in-place vibe check. If you get asked this in 2024, keep your code tight and your sarcasm tighter.