219. Contains Duplicate II

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.

Examples

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
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def containsNearbyDuplicate(nums: List[int], k: int) -> bool:
    window = set()
    left = 0
    
    for right in range(len(nums)):
        if right - left > k:
            window.remove(nums[left])
            left += 1
        
        if nums[right] in window:
            return True
        
        window.add(nums[right])
    
    return False

Alternative Solution (Using Dictionary):


def containsNearbyDuplicate(nums: List[int], k: int) -> bool:
    last_seen = {}
    
    for i, num in enumerate(nums):
        if num in last_seen and i - last_seen[num] <= k:
            return True
        last_seen[num] = i
    
    return False

Java Solution


class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set window = new HashSet<>();
        int left = 0;
        
        for (int right = 0; right < nums.length; right++) {
            if (right - left > k) {
                window.remove(nums[left]);
                left++;
            }
            
            if (window.contains(nums[right])) {
                return true;
            }
            
            window.add(nums[right]);
        }
        
        return false;
    }
}

C++ Solution


class Solution {
public:
    bool containsNearbyDuplicate(vector& nums, int k) {
        unordered_set window;
        int left = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            if (right - left > k) {
                window.erase(nums[left]);
                left++;
            }
            
            if (window.count(nums[right])) {
                return true;
            }
            
            window.insert(nums[right]);
        }
        
        return false;
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    const window = new Set();
    let left = 0;
    
    for (let right = 0; right < nums.length; right++) {
        if (right - left > k) {
            window.delete(nums[left]);
            left++;
        }
        
        if (window.has(nums[right])) {
            return true;
        }
        
        window.add(nums[right]);
    }
    
    return false;
};

C# Solution


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

Complexity Analysis

Solution Explanation

There are two main approaches to solve this problem:

Key Points

Optimization Tips

Edge Cases