219. Contains Duplicate II

Time: O(n)

Space: O(n)

Intuition

Use a sliding window of size k maintained as a HashSet. As the window slides, add the new element and check if it was already present. If the window size exceeds k, remove the oldest element.

Algorithm

1window = HashSet.
2For i from 0 to n-1: if window.Contains(nums[i]), return true.
3window.Add(nums[i]). If window.Count > k, window.Remove(nums[i-k]).
4Return false.

Example Walkthrough

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

1.i=0: add 1. i=1: add 2. i=2: add 3. i=3: 1 is in window -> return true.

Output: true

Common Pitfalls

•Check for duplicate BEFORE adding to the window and BEFORE removing the oldest element.

219.cs

// Approach: HashMap stores the most recent index at which each value was seen.
// For each element nums[i]: if nums[i] already exists in the map and i - map[nums[i]] <= k, return true.
// Otherwise update the map with the current index.
// This single-pass approach uses the last seen index, which gives the smallest possible gap.
// Time: O(n) Space: O(n) for the map.

public class Solution
{
    public bool ContainsNearbyDuplicate(int[] nums, int k)
    {
        Dictionary<int, int> map = new Dictionary<int, int>();
        int n = nums.Length;

        for (int i = 0; i < n; i++)
        {
            if (map.ContainsKey(nums[i]))
            {
                int prevIndex = map[nums[i]];
                int value = Math.Abs(prevIndex - i);
                if (value <= k)
                    return true;
                map[nums[i]] = i;
            }
            else
            {
                map.Add(nums[i], i);
            }
        }

        return false;
    }
}

Was this solution helpful?