Contains Duplicate II

LeetCode 219 | Difficulty: Easy

Easy

Problem Description

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.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Constraints:

- `1 <= nums.length <= 10^5`

- `-10^9 <= nums[i] <= 10^9`

- `0 <= k <= 10^5`

Topics: Array, Hash Table, Sliding Window

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 228 ms)

Metric	Value
Runtime	228 ms
Memory	50.6 MB
Date	2022-01-16

Solution

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

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.