Contains Duplicate II

From Brute Force to Index-Based Frequency Thinking

At first glance, Contains Duplicate II looks simple:
“Check if a number repeats within distance k.”

My first solution worked — but it was slow.

This article shows:

• My initial brute-force thinking
• Why simple frequency count is not enough
• The optimized approach using a hash map
• A debugger-style explanation of the tricky lines

🧩 Problem Summary

You are given:

An array nums
An integer k

Return true if there exist two equal values such that
the absolute difference of their indices ≤ k.

❌ My First Approach (Brute Force) Idea

1. Check every pair (i, j) and see if
2. values are equal
3. index difference ≤ k

Code

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                if(nums[i] == nums[j] && abs(i - j) <= k)
                    return true;
            }
        }
        return false;
    }
};

Problem ❌

Time complexity: O(n²)
TLE for large inputs

🤔 Can We Use Frequency Count?

Short answer: Not directly
A normal frequency map only tells:

2 → appears 3 times

But this problem asks:

HOW CLOSE are the indices?

So we need:

Last seen index, not count. This is the key insight 🔑

✅ Optimized Idea (Index-Based Frequency)

Instead of counting occurrences. Store last index where a number appeared

Data structure:

unordered_map<int, int> lastIndex;

Meaning:

number → last index seen

💻 Full Working C++ Code (With main)

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int, int> lastIndex;

    for (int i = 0; i < nums.size(); i++) {

        // Check if number already exists
        if (lastIndex.count(nums[i]) && i - lastIndex[nums[i]] <= k)
            return true;

        // Update last seen index
        lastIndex[nums[i]] = i;
    }
    return false;
}

int main() {
    vector<int> nums = {1, 2, 3, 1};
    int k = 3;

    cout << (containsNearbyDuplicate(nums, k) ? "true" : "false");
    return 0;
}

🐞 Debugger-Style Explanation (Line by Line)

The Tricky Line 👇

if (lastIndex.count(nums[i]) && i - lastIndex[nums[i]] <= k)

Let’s break it slowly.

🔍lastIndex.count(nums[i])

👉 IMPORTANT CLARIFICATION

❗ count() does NOT count frequency

It only checks existence.Returns 1 → key exists. Returns 0 → key does not exist

So this line means:

Have I seen nums[i] before? . Nothing more.

🔍lastIndex[nums[i]]

This holds:

The LAST index where nums[i] appeared

Example:

nums = [1, 2, 3, 1]
index = 3

Map before checking:

1 → 0
2 → 1
3 → 2

So:

lastIndex[1] = 0

🔍i - lastIndex[nums[i]]

This calculates:

current index - previous index

Example:

i = 3
lastIndex[1] = 0

distance = 3 - 0 = 3

This is exactly what the problem asks.

🔍 Full Condition in Plain English

if (
   "I have seen this number before"
   AND
   "distance between indices ≤ k"
)


→ return true.

🔄 Visualization

For:

nums = [1, 2, 3, 1], k = 3

i	nums[i]	lastIndex before	distance	result
0	1	not found	—	store 1 → 0
1	2	not found	—	store 2 → 1
2	3	not found	—	store 3 → 2
3	1	found (0)	3	✅ true

✅ What I Learned Now

1. count() only checks existence
2. Hash maps can store indices, not just counts
3. Frequency count ≠ position tracking
4. This is a single-pass O(n) solution

❌ What I Didn’t Know Before

• That distance problems need index memory
• That frequency maps can mean different things
• Why brute force fails even when logic is correct

🎯 Final Takeaway

When a problem mentions distance between indices,
counting is not enough — track positions.

This pattern appears again in:

Longest substring without repeating characters
Sliding window problems
Index-based hashing questions

Comments

[Charles Kumar]

🐞 Debugger-Style Explanation is nice to comprehend

the pivotal line

if (lastIndex.count(nums[i]) && i - lastIndex[nums[i]] <= k)

Explanation in Plain English is more humane

if (
   "I have seen this number before"
   AND
   "distance between indices ≤ k"
)


→ return true.