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

Source: leetcode | Difficulty: EASY
Tags: Data structures

Amortized analysis

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

Solutions:
class Solution:

	def containsNearbyDuplicate(self, nums, k):
		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):
		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):
		m = {}
		for (i, n) in enumerate(nums):
			if n in m and abs(m[n] - i) <= k:
				return True
			m[n] = i
		return False


class Solution:

	def containsNearbyDuplicate(self, nums, k):
		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):
		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):
		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):
		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):
		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):
		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):
		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):
		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