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

In my opinion it is more like hard problem, because brute-force solution will get you TLE and all other solutions uses some not easy trick: either heaps or BST or bucket sort. If you know some other solution without these ideas, please let me know!

In this problem we need to iterate over window of size k+1 and check if there is numbers with difference <=t in this window. What we need to do efficiently is to add and remove elements from our window, and my choice of data structure is BST, which is implemented in SortedList in python. So on each step we have sorted list of elements in this window. Imagine the case:

[1, 3, 7, 12] and new number we need to insert is 10, and t = 2. Then we need to consider range [8,12] and check if we have numbers in our SList in this range. We can do two binary searches here: bisect_left for left boundary and bisect_right for right boundary. Also we need to check if pos1 != len(SList), if this is the case, it means that new number is bigger than bigges number in list + t, so in this case we just put it directly to our list. If pos1 != pos2, this means, that we found some number i our [nums[i] - t, nums[i] + t] range, so we immediatly return True.

Complexity: time complexity is O(n log k), because we do n steps, each one with O(log k) complexity to do binary search, remove and add elements. Space complexity is O(k) to keep our SortedList updated.

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

Another idea is that we do not really need maximum and minimum in each window, only the difference. We can use the idea of bucket sort, where we put every number $i$ to the bucket with number $\frac{i}{t+1}$. Then if we have two numbers in one bucket, we immediately return \texttt{True}. Also we need to check only two neighbors for each bucket. Finally, we go through numbers, put them to buckets and always keep number of buckets no more than $k$. Overall time complexity is $O(n)$ and space complexity is $O(k)$ to keep dictionary of bucketNumb: index.

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        if t < 0: return False
        n, d, w = len(nums), {}, t + 1
        for i in range(n):
            m = nums[i] // w
            for neib in [m-1, m, m+1]:
                if neib in d and abs(nums[i] - d[neib]) < w:
                    return True

            d[m] = nums[i]
            if i >= k: del d[nums[i - k] // w]
        return False

If you like the solution, you can upvote it on leetcode discussion section: Problem 0220