In this Leetcode Contains Duplicate II problem solution we have 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.

Leetcode Contains Duplicate II problem solution


Problem solution in Python.

class Solution:
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return len(list(set(nums))) < len(nums)



Problem solution in Java.

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int end = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            end = i + 1;
            while (end < nums.length && nums[end] != nums[i]) {
                end++;
            }
                        //no duplicate value for nums[i]
            if (end >= nums.length) continue;
            if (nums[end] == nums[i] && end - i <= k) {
                return true;
            }
        }
        return false;
    }
}


Problem solution in C++.

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


Problem solution in C.

typedef struct Node{
    int latest_index;
    int key;
    int val;
    struct Node *next;
};

#define SIZE 1000
int getPos(int n){
    long long num=n;
    if(num<0)
        num=-1*num;
    return num%SIZE;
}

bool containsNearbyDuplicate(int* nums, int numsSize, int k){
    struct Node** hashMap=calloc(SIZE+1, sizeof(struct Node *));
    for(int i=0;i<numsSize;i++){
        int pos=getPos(nums[i]);
        struct Node* iter=hashMap[pos];
        struct Node* prev=hashMap[pos];
        while(iter){
            if(iter->key==nums[i]){
                if(iter->val>=1){
                    if(i <= iter->latest_index+k){
                        return true;
                    }
                }
                iter->latest_index=i;
                iter->val++;
                break;
            }
            prev=iter;
            iter=iter->next;
        }
        if(iter==NULL){
            struct Node *tmp=malloc(sizeof(struct Node));
            tmp->key=nums[i];
            tmp->val=1;
            tmp->latest_index=i;
            tmp->next=NULL;
            if(prev){
                prev->next=iter;
            }
            else{
                hashMap[pos]=tmp;
            }
        }
    }
    
    return false;
}