Contains Duplicate II

1. Define the problem

Given an integer array nums and an integer k, return true if there are two distinct indices i and j such that nums_i === nums_j and abs(i - j) ≤ k. Keep a sliding set of recent values so duplicates are found when they are at most k indices apart.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums_i ≤ 10⁹
0 ≤ k ≤ 10⁵

Example

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

Outputtrue

Explanation nums₀ === nums₃ === 1, and |0 - 3| = 3 ≤ 3.

2. Know the words first

In plain terms

Distinct indices: Two different positions in the array — like slot 2 and slot 5 — not the same spot counted twice, even if the values stored there happen to match.

3. Visualize the solution

Track a window of the last k values

Statusadd

right=0: 1 is new — add to the set. Window size 1 ≤ k.

What happens in this step

set before = {}
check: is nums[0] = 1 in the set? no
add nums[0] = 1 → set = {1}

size = 1 ≤ k = 3, so nothing needs to be dropped yet.

Step 1 of 4

Steps to visualize

Move right across the array and check if the current value is already in the set.
If it is, a duplicate sits within distance k — return true.
Otherwise add the value to the window set.
When the set grows past k, drop the leftmost value that left the window.
If you finish with no hit, return false.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track a window of the last k values

Statusadd

right=0: 1 is new — add to the set. Window size 1 ≤ k.

What happens in this step

set before = {}
check: is nums[0] = 1 in the set? no
add nums[0] = 1 → set = {1}

size = 1 ≤ k = 3, so nothing needs to be dropped yet.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function containsNearbyDuplicate(nums, k) {
  const window = new Set();

  for (let right = 0; right < nums.length; right++) {
    if (window.has(nums[right])) {
      return true;
    }
    window.add(nums[right]);

    if (window.size > k) {
      const left = right - k;
      window.delete(nums[left]);
    }
  }

  return false;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 2, 3, 1], k = 3`	`true`	example from the docstring
`nums = [1], k = 1`	`false`	smallest valid input: single element, no duplicate possible
`nums = [1, 1, 1], k = 0`	`false`	k === 0 never matches anything (no distinct index pair)
`nums = [1, 2, 3, 4, 5, 2], k = 5`	`true`	window must slide across the whole array before finding the match
`nums = [7, 7, 7, 7], k = 1`	`true`	all identical elements always matches
`nums = [1, 2, 3, 1], k = 2`	`false`	no valid answer: duplicates exist but are farther apart than k
`nums = [0, 9, 2, 4, 3, 5, 6, 4, 9], k = 3`	`false`	larger, hand-verified case
`nums = [0, 9, 2, 4, 3, 4, 6], k = 2`	`true`	larger case with a real match within range

Contains Duplicate II