Problem statement

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.

Example 1

Input: nums = [1,2,3,1], k = 3
Output: true
Explanation: The two 1s sit at indices 0 and 3, and 3 - 0 <= 3.

Example 2

Input: nums = [1,0,1,1], k = 1
Output: true
Explanation: Indices 2 and 3.

Example 3

Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Explanation: Every repeat is three apart.

Constraints

• 1 <= nums.length <= 40
• -1000 <= nums[i] <= 1000
• 0 <= k <= 40

Hints for Contains Duplicate II

1. Hint 1

   Only the most recent index of each value matters — an older one is strictly further away.

2. Hint 2

   Keep a map from value to its last index and compare distances as you scan.

3. Hint 3

   Equivalently, slide a window of size k and keep a set of the values inside it.

How to solve Contains Duplicate II

Only the most recent index of each value matters: any older copy is further away. Keep a map from value to its last index and check the gap on every repeat.

Approach

1. Scan with a map last from value to index.
2. At index i, if x is in last and i - last[x] <= k, return true.
3. Set last[x] = i and continue; return false at the end.

Why it works

If some pair of equal values sits within k, the later of the two sees the earlier one (or an even closer copy) as last[x], so the check fires. Overwriting with the newer index can only shrink future gaps.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The condition is <= k, not < k.
• A sliding window with a set of the last k values is equivalent and bounds memory by k.

Reference solution

Python

def containsNearbyDuplicate(nums, k):
    last = {}
    for i, x in enumerate(nums):
        if x in last and i - last[x] <= k:
            return True
        last[x] = i
    return False

Java

public static boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> last = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        Integer prev = last.get(nums[i]);
        if (prev != null && i - prev <= k) return true;
        last.put(nums[i], i);
    }
    return false;
}

C++

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int, int> last;
    for (int i = 0; i < (int) nums.size(); i++) {
        if (last.count(nums[i]) && i - last[nums[i]] <= k) return true;
        last[nums[i]] = i;
    }
    return false;
}

JavaScript

var containsNearbyDuplicate = function(nums, k) {
    const last = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (last.has(nums[i]) && i - last.get(nums[i]) <= k) return true;
        last.set(nums[i], i);
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy