EasyArrayHash TableSliding WindowUpdated Sep 2026

219. Contains Duplicate II

Asked at Google, Netflix

Difficulty

Easy

Time

O(n)

Space

O(n)

Pattern

Array

Companies

2

Problem

You are given an integer array nums and an integer k. Decide whether the array contains the same value twice at two different positions that are close together.

"Close together" means the distance between the two positions is at most k. If the positions are i and j, then i != j, nums[i] == nums[j], and abs(i - j) <= k must all hold. Return true if at least one such pair exists, otherwise return false.

A simple way to think about it: slide a window of width k over the array. If any value appears twice inside the same window, the answer is true.

Two equal values within distance k

numsdistance 3 <= k12310123Both marked cells hold 1, and their index gap is 3
In [1,2,3,1] with k = 3, the two 1s sit 3 apart, which is allowed, so the answer is true.

Constraints

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

Examples

Example 1
Inputnums = [1,2,3,1], k = 3
Outputtrue
WhyThe value 1 appears at index 0 and index 3. The gap is 3 - 0 = 3, which is not more than k = 3, so the pair is valid.
Example 2
Inputnums = [1,0,1,1], k = 1
Outputtrue
WhyThe value 1 appears at indices 0, 2 and 3. Indices 2 and 3 are only 1 apart, and 1 <= k = 1, so we return true.
Example 3
Inputnums = [1,2,3,1,2,3], k = 2
Outputfalse
WhyEvery repeated value is 3 positions away from its earlier copy (1 at 0 and 3, 2 at 1 and 4, 3 at 2 and 5). Since 3 > k = 2, none of these pairs is close enough.

Asked At

2 companies
CompanyDifficulty
GoogleEasyView all Google questions →
NetflixEasyView all Netflix questions →

How to Think About It

1

Brute force: for each element, check the next k elements for a duplicate. That's O(n * k). Too slow for large k.

2

Better: use a hash set as a sliding window of size k. For each element, check if it's in the set. If yes, return true. Then add the element. If the window exceeds size k, remove the oldest element. O(n) time, O(k) space.

3

Optimal: use a hash map storing the last seen index of each element. For each element, if it's in the map and the stored index is at least i - k, return true. Update the stored index. O(n) time, O(n) space.

4

Edge cases: k=0 (no valid pair since i != j), single element (return false), all elements same (return true if k >= 1).

Optimal Approach

Use a hash map storing each element's last seen index. For each element at index i:

  1. If the element is in the map and i - map[element] <= k, return true.
  2. Update map[element] = i.

The map naturally handles the k-distance constraint: if the stored index is too far back (> k), it won't satisfy the condition. Updating to the latest index ensures future comparisons use the closest match.

Time: O(n) -- single pass. Space: O(n) for the hash map.

Remember the last index of each value

nums12310123iStep 1 — indices 0..2 are new values, so we justrecord them in the mapnums12310123iStep 2 — value 1 was last seen at index 0, and 3 − 0 =3 <= k, so return trueif num in seen and i - seen[num] <= k: return trueseen[num] = i
We keep a map value → last index seen. A hit is only useful if the stored index is within k of the current one.
ComplexityTime O(n)Space O(n)One pass over the array, and the hash map may hold up to n distinct values in the worst case.

What Trips People Up in Real Interviews

1

Using a sliding window hash set instead of a hash map. A set tells you IF the element is in the window but not WHERE. You need the index to check the distance constraint.

2

Forgetting that the stored index might be outside the k-distance window. If i - seen[num] > k, it's a valid duplicate but too far apart. Update the stored index to the current one.

3

Confusing absolute difference with exact difference. The problem says abs(i - j) <= k, which means the distance in either direction. Since we iterate left to right, we only need to check if i - seen[num] <= k.

4

Not updating the stored index. If you keep the first occurrence, a later duplicate might falsely match against a distant first occurrence. Always update to the latest index.

5

Returning true when k=0. With k=0, the only pair is (i, i) which is not two distinct indices. Return false for k=0.

Solution Code

O(n) time
def containsNearbyDuplicate(nums, k):
    seen = {}
    for i, num in enumerate(nums):
        if num in seen and i - seen[num] <= k:
            return True
        seen[num] = i
    return False

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Contains Duplicate II problem?

Given an integer array and an integer k, determine if there are two distinct indices i and j such that `nums[i]` == `nums[j]` and the absolute difference between i and j is at most k. This is a sliding window problem with hash map tracking.

How do you solve Contains Duplicate II?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Contains Duplicate II?

Contains Duplicate II is asked at Google, Netflix. It is a easy difficulty problem.

What are common mistakes on Contains Duplicate II?
  • Using a sliding window `hash set` instead of a `hash map`. A set tells you IF the element is in the window but not WHERE. You need the index to check the distance constraint.
  • Forgetting that the stored index might be outside the k-distance window. If `i - seen[num] > k`, it's a valid duplicate but too far apart. Update the stored index to the current one.
  • Confusing absolute difference with exact difference. The problem says abs(i - j) <= k, which means the distance in either direction. Since we iterate left to right, we only need to check if `i - seen[num] <= k`.
  • Not updating the stored index. If you keep the first occurrence, a later duplicate might falsely match against a distant first occurrence. Always update to the latest index.
  • Returning true when k=0. With k=0, the only pair is (i, i) which is not two distinct indices. Return false for k=0.