Leetcode: Contains Duplicate II
Given an array nums
and a number 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
.
The solution involves two pointers that are at most k
items apart. The items are stored in a set and if there’s a duplication, True
will be returned. Otherwise False
.
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
curr_nums = set()
p1 = 0
p2 = 0
while p1 < len(nums):
if nums[p1] in curr_nums:
return True
curr_nums.add(nums[p1])
if p1 - p2 >= k:
curr_nums.remove(nums[p2])
p2 += 1
p1 += 1
return False
O(n)
and space complexity is O(k)
.