A sensor logs one reading per second in nums. A glitch shows up as the same reading twice, close together. Write repeat_within(nums: list[int], k: int) -> bool that returns True if there are two different indexes i and j with nums[i] == nums[j] and |i - j| <= k.
repeat_within([4, 7, 2, 7], 2) # True (the 7s are 2 apart)
repeat_within([4, 7, 2, 4], 2) # False (the 4s are 3 apart)
repeat_within([5, 5], 1) # True
repeat_within([1, 2, 3, 1, 2], 0) # False (k = 0 allows no pairs)
1 <= len(nums) <= 2 * 10^5; values are in[-10^9, 10^9];0 <= k <= 10^9(kmay be larger than the list).- Comparing each reading with the next
kis O(n·k), too slow whenkis large. Aim for O(n) expected time.
Show hint
as you scan, you only care about the last k readings before the current one. Keep exactly those in a structure with O(1) lookups, adding the newest and dropping the one that falls out of range.