220.-contains-duplicate-iii.md

220. Contains Duplicate III

• Medium
• Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.

Analysis

This is a sliding window problem. The problem is that whether we take a window of size k and test if there are numbers in it that is has difference less than t, or we can keep windows or buckets of size t and see if there are numbers inside the same bucket that has index difference less than k.

The second idea is the one I tested first, but I couldn't find a solution to it. So the first idea is what gives us the solution.

In this solution, we keep our window as a sorted list. By looking for where the new number should be inserted, we would also see if there is a number that falls in the interval in the window(indicated by pos1!=pos2).

from sortedcontainers import SortedList

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        SList = SortedList()
        for i in range(len(nums)):
            if i > k: SList.remove(nums[i-k-1])   
            pos1 = SortedList.bisect_left(SList, nums[i] - t)
            pos2 = SortedList.bisect_right(SList, nums[i] + t)
            
            if pos1 != pos2 and pos1 != len(SList): return True
            
            SList.add(nums[i])
        
        return False