[📝LeetCode #219] Contains Duplicate II

🎀 The Problem

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:

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

👩‍💻 My Answer

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];

            if (!map.containsKey(num)) {
                map.put(num, i);
                continue;
            }

            if (i - map.get(num) <= k)
                return true;
            else
                map.put(num, i);
        }

        return false;
    }
}

Pro & Con

✅ Runtime & Memory
🔺 Maybe there is a better one?

💋 Ideal Answer

Approach - "HashSet"

I read the solution post on LeetCode and found the HashSet approach, which was faster than my code. (Beats 98%)

Here is the code that I found on LeetCode.

New Code

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            if(i > k) set.remove(nums[i-k-1]); //remove element if its distance to nums[i] is not lesser than k
            if(!set.add(nums[i])) return true; //because all still existed elements is closer than k distance to the num[i], therefore if the add() return false, it means there's a same value element already existed within the distance k, therefore return true.
        }
        return false;
 }
}

I'm not 100% sure why the HashSet is faster than HashMap. (Both time and space complexity are O(N)). So, I asked in the comment section. If I get a reply, I will update here! Also, I'm thinking of writing a new post to compare the HashMap vs HashSet.

(Or if you know, please comment here!)

💡 What I Learned

I finally wrote decent, efficient code by myself for the first time to solve LeetCode.
Although I know how to use HashMap or HashSet, I still do not know that how operation is going on under the code;((((

shine @shine7on