Contains Duplicate II

SLIDING WINDOW · EASY

Builds on Day 5: Sliding Window Pattern

The optimal solution below maintains a window of the last k elements as it slides across the array; read that lesson first if the “grow/shrink a window as you scan” mental model is still new.

The problem

You’re given an integer array nums and an integer k. Return true if there exist two distinct indices i and j such that nums[i] === nums[j] and Math.abs(i - j) <= k. In plain words: it’s not enough for a value to repeat somewhere in the array — the two matching indices also have to be close enough together, within k positions of each other. For example, nums=[1,2,3,1], k=3 is true (indices 0 and 3, distance exactly 3, which is <= 3). But nums=[1,2,3,1,2,3], k=2 is false — the repeated 1 is at indices 0 and 3, a distance of 3, which is too far apart for k=2, and no other pair is close enough either.

Solution 1: Brute force — bounded pair scan

The most direct reading of the problem: for every index i, look at every other index j that’s within distance k and see if the values match. It would be wasteful to compare i against every single other index in the array — the problem only cares about pairs within distance k, so the inner loop can be bounded to j <= i + k instead of scanning all the way to the end. That bound makes this a genuine, if modest, improvement over a fully naive all-pairs scan — it’s still fundamentally checking pairs one at a time with no memory of what’s been seen, which is what makes it “brute force,” but the exact cost is O(n·k), not O(n²).

nums = [1, 0, 1, 1], k = 1 — bounded inner loop finds match at indices 2 and 3

Press play to run the brute force algorithm.

comparisons: —

Step 0 / 5

▶ Play — O(n·k)↺ Reset

The code

function containsNearbyDuplicateBruteForce(nums, k) {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j <= i + k && j < n; j++) {
      if (nums[i] === nums[j]) return true;
    }
  }
  return false;
}

Line by line:

• The outer loop visits every index i exactly once — a plain left-to-right scan.
• The inner loop’s condition is j <= i + k && j < n — two bounds at once. j <= i + k stops the loop from ever comparing indices more than k apart (the problem doesn’t care about farther pairs), and j < n just guards against walking off the end of the array near the end of the scan.
• if (nums[i] === nums[j]) return true; — the instant a matching pair inside the distance bound is found, the function returns immediately. No need to keep scanning once one qualifying pair exists.
• If the nested loops finish without ever hitting that return true, no pair satisfies both conditions simultaneously, so the function falls through to return false.

Complexity

Time	Space	Approach
O(n·k)	O(1)	Bounded pair scan — inner loop capped at k comparisons per i, no auxiliary structure

Solution 2: Optimal — sliding window with a hash set

Instead of re-checking a window of indices from scratch at every i, maintain a Set that always holds exactly the last k values seen — a literal sliding window, implemented as a hash set instead of an index range. For each index i, the order of operations matters and has to happen in exactly this sequence: first check whether nums[i] is already in the set (if so, a duplicate within distance k exists — return true immediately); then add nums[i] to the set; then, only if the set has grown past size k, remove the value that just fell more than k positions behind (nums[i - k]) to keep the window’s size bounded. Checking before adding is what keeps a value from ever matching against itself, and trimming only after adding is what keeps the window’s size correct at every step.

nums = [1, 2, 3, 1, 2, 3], k = 2 — sliding window Set keeps the last k values; the repeated 1 is dropped before index 3 is reached

Press play to run the optimal algorithm.

window size: —

Step 0 / 14

▶ Play — O(n)↺ Reset

The code

function containsNearbyDuplicateOptimal(nums, k) {
  const window = new Set();
  for (let i = 0; i < nums.length; i++) {
    if (window.has(nums[i])) return true;
    window.add(nums[i]);
    if (window.size > k) {
      window.delete(nums[i - k]);
    }
  }
  return false;
}

Line by line:

• window is a Set that, at the top of every loop iteration, holds exactly the values at indices [max(0, i-k), i-1] — the last up-to-k values seen so far, and nothing older.
• if (window.has(nums[i])) return true; — this check happens before nums[i] is added to the set. That order is essential: if the current value is already in the window, it means some earlier index within the last k positions had the same value, which is exactly the condition the problem asks for. Checking after adding would make every value match against itself.
• window.add(nums[i]) only runs for values that weren’t already in the window — by this point, nums[i] is guaranteed new to the current window.
• if (window.size > k) window.delete(nums[i - k]); — this only fires once the window has grown one element past its allowed size. The value being removed, nums[i - k], is always exactly the one that just became more than k positions behind the current index — removing it (rather than any arbitrary element) is what keeps the set an accurate sliding window instead of an ever-growing “seen so far” set.

Complexity

Time	Space	Approach
O(n)	O(min(n, k))	Sliding-window hash set — check, add, then trim, each value touched a constant number of times

Complexity comparison

Solution	Time	Space
Brute force (bounded pair scan)	O(n·k)	O(1)
Optimal (sliding window set)	O(n)	O(min(n, k))

This is a genuine, honest time improvement when k is large — up to O(n) when k approaches the array’s length, the bounded brute force degrades toward O(n²), while the sliding window stays flat at O(n). But be precise about the other direction too: when k is small or effectively constant, O(n·k) and O(n) are close in practice — the brute force is only ever doing a small, bounded amount of extra work per index either way. The optimal solution’s real, unconditional win is trading that per-index scan for O(1) amortized set operations, at the cost of O(min(n, k)) extra space instead of the brute force’s O(1).

Interview corner

Why does the optimal solution check window.has(nums[i]) before calling window.add(nums[i]), instead of adding first and then checking?

• The window is supposed to represent values seen at earlier indices, strictly before i. If the current value were added first, then the very next line’s check would always find it — every element would trivially “match itself,” and the function would return true on the very first iteration, every time.
• Checking first is what correctly captures the problem’s requirement of two distinct indices — the check can only ever succeed against a value that was placed into the set during some previous, different iteration.
• This ordering — check, then add, then (conditionally) trim — has to happen in exactly that sequence every iteration; reordering any two of those three steps breaks correctness in a different way for each swap.

Why is the value removed during trimming always nums[i - k] specifically, and not simply “the oldest value in the set” or the minimum value?

• The window is meant to represent an exact range of indices — [i-k, i-1] right before processing index i — not an unordered bag of “recently seen” values. nums[i - k] is the one specific index that just crossed from “within distance k” to “more than k positions behind.”
• “Oldest value in the set” isn’t well-defined for a plain Set in the first place — a Set preserves insertion order for iteration, but nothing about its API exposes “the earliest inserted value” in O(1); computing that separately would require extra bookkeeping (like a companion queue of indices), which the index arithmetic nums[i - k] avoids entirely.
• Removing anything other than exactly nums[i - k] — e.g. removing an arbitrary or a “minimum” value — could either evict a value that’s still within the valid distance-k range (causing a real duplicate to be missed) or fail to evict a value that’s now too far away (causing a false positive on a pair that’s actually too far apart).

↳ Common follow-up: “What if two different indices in the current window share the same value?” That can’t happen here — the moment a repeat would be added, the has() check on the line above already caught it and returned true, so by the time window.add runs, the set is guaranteed to still contain only distinct values.

The brute force bounds its inner loop to j <= i + k instead of scanning to the end of the array. Is that enough to call it “optimal,” or is the sliding window still a genuine improvement?

• The bound is a real, honest improvement over a fully naive all-pairs O(n²) scan — it’s O(n·k), not O(n²) — because it skips comparing indices that could never satisfy the distance constraint anyway.
• But it’s still doing repeated, redundant work: at every single index i, it re-examines up to k neighboring values from scratch, even though most of that work was already effectively done one iteration ago. The sliding window’s Set carries that information forward instead of re-deriving it.
• The honest comparison is O(n·k) vs. O(n) — a real asymptotic win when k is large, and a modest, practical-but-not-asymptotic difference when k is small. Calling the bounded brute force “already optimal” would only be fair if the problem’s k were guaranteed small and constant — which it isn’t.

Trick question — this problem is defined over ordinary integers, so NaN never actually appears in a real nums input. But suppose it did. Would the brute force and the optimal solution above still agree with each other on an array containing two NaN values within distance k?

console.log(NaN === NaN);            // ?
console.log(new Set([NaN]).has(NaN)); // ?

• Answer: false, then true — the two solutions would actually disagree on hypothetical NaN input.
• The brute force compares with nums[i] === nums[j], strict equality, and NaN === NaN is famously false — so two NaNs, no matter how close together, would never register as a match. It would return false.
• The optimal solution’s window.has(nums[i]) uses a Set’s membership check, which relies on SameValueZero comparison instead of strict equality — and SameValueZero treats NaN as equal to itself. It would correctly return true.

⚠ Trap: this divergence is purely academic for THIS problem — LeetCode’s constraints guarantee nums[i] is a real integer, so NaN can never occur here, and both solutions are fully correct as written for every valid input. But it’s a genuine, verified illustration of why === and Set/Map membership are NOT interchangeable comparison rules in general — swapping a hand-rolled === check for a Set-based one (or vice versa) is not always a behavior-preserving refactor once NaN is a possible value in the data.

Quiz

1. What does Contains Duplicate II actually require, beyond just nums[i] === nums[j]?

The two matching indices must also be within distance k of each other — Math.abs(i - j) <= kThe array must already be sorted before checking for duplicatesk must itself be one of the values present in the array

2. What is the honest time complexity of the brute-force solution that bounds its inner loop to j <= i + k?

O(n·k) — bounded to at most k comparisons per index, not a full n² scanO(n²) — it’s still comparing every pair of indices in the arrayO(n log n) — the bound effectively behaves like a sort

3. In the optimal solution, why must window.has(nums[i]) be checked BEFORE window.add(nums[i]), not after?

Checking after adding would make every value match against itself on the very first lookIt’s purely a performance choice with no effect on correctness either wayA Set throws an error if you call has() on a value it doesn’t contain yet

4. Why does the optimal solution remove exactly nums[i - k] when trimming the window, rather than any other element?

It’s the specific index that just became more than k positions behind i — removing any other value could break the window’s correctnessAny element can be removed — a Set’s contents are unordered, so it doesn’t matter which oneIt removes whichever value is numerically smallest, to keep the Set easy to scan

5. On a hypothetical array containing two NaN values close together, which check would fail to detect them as a match?

nums[i] === nums[j] in the brute force — strict equality treats NaN === NaN as falsewindow.has(nums[i]) in the optimal solution — Sets can never store NaNBoth checks would fail to detect it identically

Mark problem complete

More Sliding Window problems

(Related problems list to be populated by the astro site engine)