219. Contains Duplicate II

Contains Duplicate II

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 <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

Approach) Hashtable

Idea:

This is similar to the version I. The difference is that instead of only testing if there is a duplicate, we need to tell the difference between the two indices of the duplicate values.

And we care about the smallest difference.

Notice that you need to put value, and index pair into the hashmap no matter if that element already appeared.

Let's Code It!

    

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    let has = new Map()
    for(let i=0;i<nums.length;i++){
        let item = nums[i];
        if(has.has(item)){
            if(Math.abs(has.get(item) - i) <= k){
                return true;
            }
        }
        has.set(item, i)
    }
    return false;
};

Complexity 

Time Complexity
We are scanning the array from left to right only once, hence the time complexity will be O(n).


Space Complexity
We are using Set as a data structure to facilitate our computation, therefore, the space complexity should also be O(n), right? Wrong!

Approach) Brute Force

const containsNearbyDuplicate = (nums, k) => {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] == nums[j] && Math.abs(i - j) <= k) {
                return true;
            }
        }
    }
    return false;
};

Approach) Sliding Window and Set

var containsNearbyDuplicate = function(nums, k) {
    const wnd = new Set();
    for(let i=0; i<nums.length; i++){
        if(wnd.has(nums[i])) return true;
        wnd.add(nums[i]);
        if(i>=k) wnd.delete(nums[i-k]);
    }
    return false;
};

OR

const containsNearbyDuplicate = (nums, k) => {
    const set = new Set()
    let low = 0
    let high = Math.min(k + 1, nums.length)
    
	// Build initial window
    for (let i = 0; i < high; i++) {
        if (set.has(nums[i])) return true
        
        set.add(nums[i])
    }
    
	// Check remaining array
    while (high < nums.length) {
        set.delete(nums[low])
        
        if (set.has(nums[high])) return true
        
        set.add(nums[high])
        
        high++
        low++
    }
    
    return false
}

Complexity 

Time Complexity
We are scanning the Array from left to right only once, hence the time complexity will be O(n).


Space Complexity
We are using Set as a data structure to facilitate our computation, therefore, the space complexity should also be O(n), right? Wrong!

Resources:

https://github.com/PraveenMistry/leetCode

https://medium.com/@praveenmistry

Conclusion

That’s all folks! In this post, we solved LeetCode problem #219 using Sliding Window Technique.

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!