Contains Duplicate II

EasySliding WindowJuniorOpen on LeetCodeUpdated Nov 11, 2026

You're given an integer array nums and an integer k. Return true if two different indices i and j hold the same value with abs(i - j) <= k, meaning some value repeats within k positions of itself. Return false otherwise, including when every repeat is more than k positions apart. With k = 0 the answer is always false.

Examples

nums = [1,2,3,1], k = 3 returns true

The two 1s sit at indices 0 and 3, exactly 3 positions apart.

nums = [1,0,1,1], k = 1 returns true

The 1s at indices 0 and 2 are too far apart, but the 1s at indices 2 and 3 are adjacent.

nums = [1,2,3,1,2,3], k = 2 returns false

Any window of k + 1 = 3 values holds no repeat.

Every value repeats, but each repeat is 3 positions after the first copy, which is more than k.

Constraints

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

Hints

Hint 1

For a value at index i, which earlier indices could possibly be its partner?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

A match for index i can only come from the k indices just before it, so keep those values in a hash set that acts as a sliding window. At each index, if the value is already in the set, a repeat lies within k positions: return true. Otherwise add it, and once the set holds more than k values, remove nums[i - k], which is now too far back to matter. The set never holds duplicates, since a duplicate would have returned already, so its size tracks the window exactly.

Time

O(n)

Space

O(min(n, k))

Pitfall

Evicting before the check, or at the wrong size, shrinks the window by one: for [1,2,3,1], k = 3 the first 1 must still be in the set when index 3 arrives. Add first, then evict only once the set holds k + 1 values.

Solutions

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> window = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!window.add(nums[i])) return true;
            if (window.size() > k) window.remove(nums[i - k]);
        }
        return false;
    }
}

class Solution:
    def containsNearbyDuplicate(self, nums, k: int) -> bool:
        window = set()
        for i, n in enumerate(nums):
            if n in window:
                return True
            window.add(n)
            if len(window) > k:
                window.remove(nums[i - k])
        return False