**Solution**

**Contains Duplicate III** https://leetcode.com/problems/contains-duplicate-iii/

**Brute Force Solution**

- Brute force solution is use two loops and test both the conditions. The inner loop starts from i+1 to i+k. Because of that, we no longer need to test one of the conditions since that is taken care of automatically.
- Time complexity : O(n * k).

```
class Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
for i in range(0, len(nums)):
for j in range(i+1, i+k+1):
if j < len(nums):
if abs(nums[i]-nums[j]) <= t:
return True
return False
```

**Binary Search Tree Solution**

- Maintain a BST of previous k elements. This is the invariant for this problem!
- When you get element x, we want to find an element y in the BST such that (y-x)<=t or (x-y)<=t
- How do we find (y-x)<=t ? Solution: Find the smallest value in the BST greater than or equal to x i.e. ceiling of x. Then test that value for the above condition.If the smallest value greater than x doesnt meet the criterion, then no other value y greater than x will meet the condition. One may consider the smallest element y that is greater or equal to x as the successor of x in the BST, as in: "What is the next greater value of x?"
- How do we find (x-y)<=t? Find the greatest element y in the BST which is smaller than or equal to x. Again if this y doesnt meet the condition, no other y in the BST will meet the condition. We consider the greatest element y that is smaller or equal to x as the predecessor of x in the BST, as in: "What is the previous smaller value of x?
- Visualize or imagine this as x and its two closest neighbors.
- After trying the above tests, if they fail, then put x in set
- If the size of the set is larger than k, remove the oldest item - this maintains the invariant.
- Time complexity : O(n * log (min(n,k))). Space complexity: O(min(n,k))

**Buckets Method**

- Maintain buckets each of size t+1 holding the last k elements. This is the invariant.
- Buckets are [0, t], [t+1,2t+1], [2t+2, 3t+2],....
- What are the conditions of a match? Either x lies in a bucket which already has a member (this directly means that x and this element are within t of each other). Or the two neighbors of around this bucket may have a potential match. Check the code for an explanation.
- Lastly we notice how we purge elements from the cache/buckets which are stale i.e. outside the window of k elements.
- Notice one more thing: -3//5 = -1 - Python does this automatically and hence we dont need any special magic for handling negative numbers.

```
class Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
if t < 0:
return False
cache = {}
for i in range(len(nums)):
if i-k > 0:
bucket_id_to_delete = nums[i-k-1]//(t+1)
del cache[bucket_id_to_delete]
bucket_id = nums[i]//(t+1)
condition1 = (bucket_id in cache)
condition2 = ((bucket_id-1 in cache and abs(cache[bucket_id-1]-nums[i])<= t))
condition3 = ((bucket_id+1 in cache and abs(cache[bucket_id+1]-nums[i])<= t))
if condition1 or condition2 or condition3:
return True
cache[bucket_id] = nums[i]
return False
```