Problem Statement

Contains Duplicate II

You are given a list of numbers called nums and a number k. Your job is to answer one yes or no question: are there two equal numbers that sit close together in the list? "Close together" means their positions are no more than k apart. In math terms, you want two different spots i and j where nums[i] equals nums[j] and abs(i - j) is k or less. The trick we will use is a sliding window. Picture a window on a train that only lets you see the last k cars you passed. As you walk down the list, the window slides forward, always showing the most recent k numbers. To check what is in the window fast, we use a hash set. A hash set is like a bag where you can drop items in and instantly ask "is this item already in the bag?" without searching one by one. If the number you are looking at is already in the bag, you found a close duplicate.

easyHash TableArrays & HashingTime: O(n) · Space: O(min(n, k))

Signals to notice

duplicate within k distancecheck if any two equal elements are ≤ k apartsliding window hash set

Brute force first

For each element, scan next k elements — O(nk).

The key insight

Maintain a hash set of the last k elements. If new element is in the set, return true. If set size > k, remove the oldest. O(n).

Trace it on `nums=[1,2,3,1], k=3`

start: window={}
i=0, nums[0]=1: not in window -> add -> window={1}, size 1 <= 3
i=1, nums[1]=2: not in window -> add -> window={1,2}, size 2 <= 3
i=2, nums[2]=3: not in window -> add -> window={1,2,3}, size 3 <= 3
i=3, nums[3]=1: 1 IS in window -> return True
answer: True (nums[0]==nums[3], |0-3|=3 <= 3)

What must stay true

The set always contains exactly the last k elements. If a duplicate falls within this window, it's detected immediately.

Shape of the loop

window = empty set
for i in range(len(nums)):
    if nums[i] in window: return True
    window.add(nums[i])
    if len(window) > k: window.remove(nums[i - k])
return False

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not removing old elements — the set must stay bounded at size k to only check within-distance duplicates.

Arrays & Hashing Pattern