Skip to main content

76. Contains Duplicate II

easyAsked at Reddit

Determine if duplicate values exist within k indices apart. Reddit uses this to test sliding-window with hash — the same shape used in their abuse pipeline to detect repeated votes from the same user_id within a short time window.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit fraud-team phone screen.

Problem

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 0 <= k <= 10^5

Examples

Example 1

Input
nums = [1,2,3,1], k = 3
Output
true

Example 2

Input
nums = [1,0,1,1], k = 1
Output
true

Example 3

Input
nums = [1,2,3,1,2,3], k = 2
Output
false

Approaches

1. Nested loop

For each i, scan j in (i, i+k] and check equality.

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

Tradeoff: O(n*k). Tight nested loop.

2. Sliding window via hash (optimal)

Maintain a window of last k elements in a set. Add new; remove the one falling out.

Time
O(n)
Space
O(k)
function containsNearbyDuplicate(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;
}

Tradeoff: Linear with sliding-window hash. Reddit's per-user-per-window abuse detection uses this exact pattern.

Reddit-specific tips

Reddit interviewers grade on the sliding-window-with-set insight. Bonus signal: connect to their per-IP burst detection (a window of recent vote IDs maintained in Redis).

Common mistakes

  • Deleting nums[i-k-1] (off by one).
  • Maintaining a Map of index instead of a Set (works but more memory).
  • Forgetting that k can be 0 (window is empty).

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Contains Duplicate III (LC 220) — fuzzy match within window.
  • Sliding Window Maximum (LC 239).
  • Longest Substring Without Repeating Characters (LC 3) — sliding window.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Set of values vs. Map of value -> last index?

Equivalent. The Map version skips the explicit eviction but uses slightly more memory.

What if k is huge (>= n)?

Degenerates to Contains Duplicate (LC 217). Hash set still works.

Practice these live with InterviewChamp.AI

Drill Contains Duplicate II and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →