Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most 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

Difficulty: introductory

Starter code:

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        

Solutions:
class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         s=set(nums)
         if len(s)==len(nums):return False
         d=dict()
         for num in nums:
             d[num]=d.get(num,0)+1
         for num in d:
             if d[num]>1:
                 index1=-1
                 index2=-1
                 for i in range(len(nums)):
                     if nums[i]==num and index1==-1:index1=i
                     elif nums[i]==num and index2==-1:index2=i
                     elif nums[i]==num and index1!=-1 and index2!=-1:
                         index1=index2
                         index2=i
                     print(index2,index1)
                     if index1!=-1 and index2!=-1 and abs(index2-index1)<=k:return True
         return False

class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         
         dic = {}
         for i, v in enumerate(nums):
             if v in dic and i - dic[v] <= k:
                 return True
             dic[v] = i
         return False


class Solution(object):
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         #Initial approach using map O(n) time and space
         m = {} #Stores value -> index mapping
         
         for i, n in enumerate(nums):
             if n in m and abs(m[n] - i) <= k:
                 return True
             #Insert new element or replace old one with index that is more right (decreases distance to next)
             m[n] = i
         
         return False
     
     '''
     Ex testcase: [1,2,3,4,5,6,7,1,9,1] k = 3
     '''

class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         if nums == None or len(nums) <= 1 or k == 0:
             return False
         maps = {}
         for i, item in enumerate(nums):
             if item in maps and abs(maps[item] - i) <= k:
                 return True
             else:
                 maps[item] = i
         
         return False

class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         hashmap = {}
         for i in range(len(nums)):
             if nums[i] in hashmap.keys():
                 if abs(i-hashmap[nums[i]]) <= k:
                     return True
                 else:
                     hashmap[nums[i]] = i
             else:
                 hashmap[nums[i]] = i
         return False

class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         hashmap = {}
         for i in range(len(nums)):
             if nums[i] in hashmap.keys():
                 if abs(i-hashmap[nums[i]]) <= k:
                     return True
                 else:
                     hashmap[nums[i]] = i
             else:
                 hashmap[nums[i]] = i
         return False

class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         d = {}
         for i, num in enumerate(nums):
             if num in d and i - d[num] <= k:
                 return True
             d[num] = i
         return False

class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         last_seen_idx = {}
         for i, num in enumerate(nums):
             if num in last_seen_idx and i - last_seen_idx[num] <= k:
                 return True
             last_seen_idx[num] = i
         
         return False

class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         s = set()
         for i in range(len(nums)):
             if i-k-1 >= 0:
                 s.remove(nums[i-k-1])
                 
             if nums[i] in s:
                 return True
             s.add(nums[i])
         return False


class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         if k == 0:
             return False
         d = {}
         for i in range(len(nums)):
             if nums[i] in d.keys() and abs(i - d[nums[i]]) <= k:
                 return True
             else:
                 d[nums[i]] = i
         return False

class Solution:
     def containsNearbyDuplicate(self, nums, k):
         if not nums or k<0 or len(nums)==len(set(nums)):
             return False
         mapD={}
         for i,v in enumerate(nums):
             if v in mapD and i-mapD[v]<=k:
                 return True
             mapD[v]=i
         return False
             


class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         if not nums or len(nums) < 2:
             return False
         
         from collections import defaultdict
         dup_idx = defaultdict(list)
         for i, num in enumerate(nums):
             dup_idx[num].append(i)
             
         for idxes in dup_idx.values():
             if len(idxes) == 1:
                 continue
             idxes = sorted(idxes)
             for i in range(1, len(idxes)):
                 if idxes[i] - idxes[i - 1] <= k:
                     return True
                 
         return False

class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         if not nums:
             return False
         d = collections.defaultdict(list)
         for i, n in enumerate(nums):
             if n in d:
                 for index in d[n]:
                     if i - index <= k:
                         return True
             d[n].append(i)
         return False

class Solution:
     def containsNearbyDuplicate(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         d = {}
         for i in range(len(nums)):
             l = d.get(nums[i], [])
             if nums[i] in d:
                 for j in l:
                     if abs(i - j) <= k:
                         return True
             l.append(i)
             d[nums[i]] = l
 
         return False