Contains Duplicate II

EasyHash Tables · Sliding Window🧩 Hashing & Counting LeetCode #219 ↗Updated Oct 30, 2026

Problem

Given an integer array nums and an integer k, decide whether some value appears at two different indices i and j that are at most k apart (|i - j| ≤ k).

Input[1,2,3,1], k=3Outputtrue

Input[1,0,1,1], k=1Outputtrue

Input[1,2,3,1,2,3], k=2Outputfalse

1 ≤ n ≤ 10⁵ · -10⁹ ≤ nums[i] ≤ 10⁹ · 0 ≤ k ≤ 10⁵

Try it yourself

Java

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

For index i only the previous k elements matter. Keep exactly those in a hash set window: a hit on insert means a close duplicate.

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForceCheck the Next k Elements

Time O(n · min(n,k))Space O(1)

For every i, compare nums[i] with each nums[j] for j in (i, i+k]. Any equal pair in that range is a valid answer.

Java

public boolean containsNearbyDuplicate(int[] nums, int k) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j <= i + k && j < nums.length; j++) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
}

No extra memory, but ~10¹⁰ comparisons when n and k are large.

BetterHash Map of Last-Seen Index

Time O(n)Space O(n)

Store each value's most recent index. When the value reappears, the nearest earlier copy is the one in the map, so i - last ≤ k is the only check needed. Older copies are always farther away.

Java

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> last = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        Integer prev = last.put(nums[i], i);   // returns old index, if any
        if (prev != null && i - prev <= k) return true;
    }
    return false;
}

Linear time, but the map keeps every distinct value ever seen.

OptimalSliding Window Hash Set

Time O(n)Space O(min(n,k))

Maintain a set holding exactly the last k values. If nums[i] is already inside, its twin is ≤ k away. After inserting, evict nums[i-k] once the set exceeds k. The window holds no duplicates (we'd have returned), so evicting by value is safe.

Java

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> window = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        if (!window.add(nums[i])) return true;   // already in window
        if (window.size() > k) window.remove(nums[i - k]);
    }
    return false;
}

Dry run[1,2,3,1,2,3], k=2

i currentw in window changed

i=1
1
w
2
i w
3

1

2

3

set={1,2}
i=2
1

2
w
3
i w
1

2

3

size 3>2 → drop 1
i=3
1

2

3
w
1
i w
2

3

1 new; drop 2
i=4
1

2

3

1
w
2
i w
3

2 new; drop 3
i=5
1

2

3

1

2
w
3
i w
3 new → false

Linear time with memory bounded by the window size.

Pro tip

Set.add returns false for an existing element — one call does both the lookup and the insert.

At a glance

Level	Approach	Time	Space
Brute Force	Check the Next k Elements	`O(n · min(n,k))`	`O(1)`
Better	Hash Map of Last-Seen Index	`O(n)`	`O(n)`
Optimal	Sliding Window Hash Set	`O(n)`	`O(min(n,k))`

Common pitfalls

Off-by-one eviction: after inserting, drop nums[i-k] (not nums[i-k-1]).
Using < k instead of ≤ k — distance exactly k counts.
Forgetting k = 0: two different indices can never be 0 apart → always false.

Interview tips

Clarify: the indices must differ, and the bound is inclusive.
Mention the map trade-off: simpler but O(n) space vs. O(k) for the window.
Bridge to Contains Duplicate III: swap the set for a TreeSet or buckets.

Pattern

Fixed-size sliding window + hash set → “does a repeat occur within distance k?”

My notes saved in this browser