easy

Contains Duplicate II

Check whether any value repeats inside a distance of at most k indices.

1. Define the problem

Contains Duplicate II

Given an integer array nums and an integer k, return true if there are two distinct indices i and j such that numsi === numsj 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 ≤ 105
  • -109 ≤ numsi ≤ 109
  • 0 ≤ k ≤ 105

Example

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

Explanation nums0 === nums3 === 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

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

  1. Move right across the array and check if the current value is already in the set.
  2. If it is, a duplicate sits within distance k — return true.
  3. Otherwise add the value to the window set.
  4. When the set grows past k, drop the leftmost value that left the window.
  5. 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

InputExpectedCovers
nums = [1, 2, 3, 1], k = 3trueexample from the docstring
nums = [1], k = 1falsesmallest valid input: single element, no duplicate possible
nums = [1, 1, 1], k = 0falsek === 0 never matches anything (no distinct index pair)
nums = [1, 2, 3, 4, 5, 2], k = 5truewindow must slide across the whole array before finding the match
nums = [7, 7, 7, 7], k = 1trueall identical elements always matches
nums = [1, 2, 3, 1], k = 2falseno valid answer: duplicates exist but are farther apart than k
nums = [0, 9, 2, 4, 3, 5, 6, 4, 9], k = 3falselarger, hand-verified case
nums = [0, 9, 2, 4, 3, 4, 6], k = 2truelarger case with a real match within range

Keep reading

TopicDescription
Sliding WindowSolve fixed-window problems: maximum sum of k elements, moving averages, and O(n) updates as the window slides.
Maximum Average Subarray IFind the contiguous subarray of a fixed length with the largest average.
Longest Substring Without Repeating CharactersFind the length of the longest run of characters in a string with no repeats.
Permutation in StringCheck whether one string contains a rearrangement of another string as a substring.
Minimum Size Subarray SumFind the shortest contiguous subarray whose sum is at least a target value.
Longest Repeating Character ReplacementFind the longest substring you can turn into one repeated letter with a limited number of swaps.