Contains Duplicate II

easy array hash map

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.

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

Outputfalse

Each repeated value is exactly 3 indices apart — outside the window.

nums (comma-separated)

def contains_nearby_duplicate(nums, k):
    last_idx = {}
    for i, v in enumerate(nums):
        if v in last_idx and i - last_idx[v] <= k:
            return True
        last_idx[v] = i
    return False

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

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

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int, int> lastIdx;
    for (int i = 0; i < (int)nums.size(); ++i) {
        auto it = lastIdx.find(nums[i]);
        if (it != lastIdx.end() && i - it->second <= k) return true;
        lastIdx[nums[i]] = i;
    }
    return false;
}

Explanation

We want to know if the same value appears twice close together — within k positions. The simple idea of comparing every pair is slow, so instead we remember where we last saw each value.

We keep a hash map last_idx that maps a value to the most recent index where it appeared. As we walk the array once, for each value v at index i we check: have we seen v before, and is the gap i - last_idx[v] at most k? If yes, we found a nearby duplicate and return true.

If not, we simply overwrite last_idx[v] = i. Keeping only the latest index is enough, because the latest position is always the closest one to any future occurrence.

Example: nums = [1,2,3,1,2,3], k = 2. When we reach the second 1 at index 3, the previous 1 was at index 0, gap 3 which is more than 2 — so it does not count. Every repeat is 3 apart, so the answer is false.

Because each step is a constant-time map lookup, we finish in a single pass over the array.

Time: O(n) Space: O(n)