219.Contains Duplicate II

📘 LeetCode 219: Contains Duplicate II

📌 Problem Overview

• Problem Number: 219
• Problem Name: Contains Duplicate II
• Difficulty: Easy
• Category: Sliding Window
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the Sliding Window algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/219.Contains-Duplicate-II/:

System.Console.WriteLine(ContainsNearbyDuplicate([1, 2, 3, 1], 3));
System.Console.WriteLine(ContainsNearbyDuplicate([1, 0, 1, 1], 1));
System.Console.WriteLine(ContainsNearbyDuplicate([1, 0, 1, 1], 1));
System.Console.WriteLine(ContainsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2)); // false
System.Console.WriteLine(ContainsNearbyDuplicate([11, 2, 3, 1, 2, 3], 2));
// ### **Problem Statement**
 
// 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]` (**the same number appears twice**)
// - The absolute difference between their indices is **at most** `k`: ∣i−j∣≤k
 
// Otherwise, return `false`.
 
 
bool ContainsNearbyDuplicate(int[] nums, int k)
{
    var dict = new Dictionary<int, int>();// Stores (value -> last index)
    
    for (var i = 0; i < nums.Length; i++)
    {
        // System.Console.WriteLine("complement: " + complement);
        // System.Console.WriteLine($"dict key{nums[i]}");
        if (dict.ContainsKey(nums[i]))
        {
            // System.Console.WriteLine($"i: {i} - dict[nums[i]]: {dict[nums[i]]}  = k {k}");
            if (i - dict[nums[i]] <= k) // Check if distance is within k
            {
                return true;
            }
        }
        dict[nums[i]] = i;
        System.Console.WriteLine($"dict: {dict[nums[i]]}");
    }
    return false;
}

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.