The O(n) Club: Contains Duplicate II: Because Sometimes Your Bugs Are Neighbors

The O(n) Club: Contains Duplicate II, Because Sometimes Your Bugs Are Neighbors

⚡ TL;DR

You’re not hunting for ordinary duplicates; you’re catching those that are dangerously “next door” (within k spots). Hash maps win. Nested loops send your CPU on holiday. Be clever:

// Naive brute-force: Don't let HR see this
for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[i] == nums[j] && Math.abs(i - j) <= k) {
            return true;
        }
    }
}
return false;

🧠 How Devs Usually Mess This Up

Caffeine levels rise, and so does the urge to check every duplicate in the array—ignoring that little ‘within k‘ detail. Or worse, you track all previous indices in some kind of reunion-list. Totally unnecessary. What you really want? Just the last time you saw that exact number, because anything before that is yesterday’s bug.

🔍 What’s Actually Going On

Picture your code as a bouncer at a club. You let new numbers in, but if you’ve seen the same guest sneak back in within k seconds, you throw the red flag. That “k-window” is your velvet rope—only the most recent entry matters. And your guest list? A hash map, recording the latest VIP spot for every number.

🛠️ PseudoCode

• Start with an empty HashMap.
• Loop: for each index i in nums:
• If nums[i] is in the map AND i - lastIndex <= k, return true immediately.
• Otherwise, update map with nums[i] → i
• If no such pair is found, return false. That’s it. No LinkedIn invitations sent to old indices.

// Java Pseudocode
def containsNearbyDuplicate(nums, k):
    map = new HashMap()
    for i in 0...nums.length-1:
        if nums[i] in map and i - map[nums[i]] <= k:
            return true
        map[nums[i]] = i
    return false

💻 The Code

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
            return true;
        }
        map.put(nums[i], i);
    }
    return false;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• k = 0? LOL, you can’t have distinct indices at zero distance. Not even Java’s off-by-one errors can make this happen.
• k >= nums.length – 1? You’re basically back to “any duplicate will do.” Why set a window if the window is the whole room?
• Tracking all indices: Don’t. You’re burning memory for nostalgia.
• Complexity: O(n) time (one-pass). O(min(n, k)) space—your map only tracks what’s relevant in the club.

🧠 Interviewer Brain-Tattoo

“A hash map is just a sliding window that hides its glass.” Impress them with your focus on constraints—even if your coffee ran out twenty minutes ago.