Leetcode 219) Contains Duplicate II

22 Nov 2021 in Algorithms

My Solution

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        /*
        1. nums[i] == nums[j]
        2.abs(i - j) <= k
        */
        //put all in map, and use the same strategy from two sum prob.

        Map<Integer,Integer> m = new HashMap<>();

        for(int i=0;i<nums.length;i++){
            if(m.containsKey(nums[i])){
                if(Math.abs(m.get(nums[i])-i)<=k){
                    return true;
                }
            }
            m.put(nums[i],i);

        }       
        return false;
    }
}

Other Solution

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i <= k && i < nums.length; ++i) {
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
        }

        for (int i = k + 1; i < nums.length; ++i) {
            set.remove(nums[i - k - 1]);
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
        }

        return false;
    }
}