219

So, we can have a dictionary, and use a foreach for the array. As we move along, we check for any duplicate. And if duplicate is found, we check the index difference (condition that we want in this problem),

If that condition is satisfied, we return true.
If not, we update the value in the dictionary to hold the latest index for that value. Because, you see, the earlier index has no chance of being used in the answer because it’s already far off.

Time - $O(n)$. Space - $O(n)$.

public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        var dict = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++)
        {
	        if (dict.ContainsKey(nums[i]))
	        {
		        if (i - dict[nums[i]] <= k) 
			        return true;
		        else 
				    dict[nums[i]] = i;
	        }
	        else
		        dict.Add(nums[i], i);
        }
        return false;
    }
}

---

Actually we can use TryGetValue, because it will avoid a second lookup,

public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        var dict = new Dictionary<int, int>();
 
        for (int i = 0; i < nums.Length; i++) {
            if (dict.TryGetValue(nums[i], out int lastIndex)) {
                if (i - lastIndex <= k)
                    return true;
            }
            dict[nums[i]] = i;
        }
 
        return false;
    }
}

---

To summarize,

We want to check if a number appears again within distance k.

Use a dictionary mapping:
value → last index where it appeared

As we iterate:

• If we see a number again:
  • Check if the distance is ≤ k → if yes, return true.
• Regardless, update the number’s latest index.

We must update to the most recent index, because earlier occurrences can never give a smaller distance.

---

Alright, there’s another approach to this problem. Using a sliding window,

Idea is,

At any index i, the window of size k behind it contains at most k elements,
[i-k, i-1]

If the current number already exists inside this window → duplicate within k distance → return true.

To maintain the window,

1. Before adding nums[i], check if it’s already in the window.
2. Add nums[i] to the window.
3. If window size > k, remove the leftmost element.

public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        var window = new HashSet<int>();
 
        for (int i = 0; i < nums.Length; i++) {
            if (window.Contains(nums[i]))
                return true;
 
            window.Add(nums[i]);
 
            if (window.Count > k)
                window.Remove(nums[i - k]);
        }
 
        return false;
    }
}

Time - $O(n)$. Space - $O(k)$.

k is the size of the sliding window (HashSet).