[LeetCode] 220. Contains Duplicate III

Problem : https://leetcode.com/problems/contains-duplicate-iii/

Maintain a section which length is K. 

For every newly inserted number nums[i], we look for is there any number >= abs(nums[i] - t).

Because the larger the 'target', the smaller 't' is.

import bisect

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        j = 0
        section = []
        for i in range(len(nums)):
            
            if i - j > k:
                # shift the section window to right
                a = bisect.bisect_left(section, nums[j])
                section.pop(a)
                j += 1
                
            target = abs(nums[i] - t)
            
            # find is there any number larger or equal to 'target'
            # a larger 'target' leads a smaller 't'
            a = bisect.bisect_left(section, target)
            if a != len(section) and abs(section[a] - nums[i]) <= t:
                return True
            
            a = bisect.bisect_left(section, -target)
            if a != len(section) and abs(section[a] - nums[i]) <= t:
                return True
            
            bisect.insort(section, nums[i])
        
        return False

Treeset solution

class TreeSet:
    def __init__(self):
        self.sortedNums = []
        
    def add(self, n):
        bisect.insort(self.sortedNums, n)
        
    def remove(self, n):
        idx = bisect.bisect_left(self.sortedNums, n)
        if idx < len(self.sortedNums) and self.sortedNums[idx] == n:
            self.sortedNums.pop(idx)
    
    def ceiling(self, n):
        idx = bisect.bisect_right(self.sortedNums, n)
        
        if idx == len(self.sortedNums) or self.sortedNums[idx] < n: return None
                       
        return self.sortedNums[idx]     
     
    def floor(self, n):
        idx = bisect.bisect_left(self.sortedNums, n)
        
        if idx == len(self.sortedNums):
            if idx - 1 >= 0:
                return self.sortedNums[idx-1]
            else:
                return None
        
        if self.sortedNums[idx] == n: return n
        
        return self.sortedNums[idx-1] if idx -1 >= 0 else None

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        treeset = TreeSet()
        
        for i in range(len(nums)):
            if i - 1 - k >= 0:
                treeset.remove(nums[i - 1 -k])
                
            s = treeset.ceiling(nums[i])
            if s != None and s <= nums[i] + t: 
                return True
            
            g = treeset.floor(nums[i])
            if g != None and g + t >= nums[i]:
                return True
                      
            treeset.add(nums[i])
            if i - k >= 0:
                treeset.remove(nums[i - k])
            
        return False

Updated 05/02/2021. Add treeset solution.