# 219. Contains Duplicate II
## Easy

## Question
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

## Thought - Map
### Python Implementation
Traversal array and build a hash table. If number exists, compare its index whether or not is within range. Be aware that EACH item needs to be added into hash table.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hashTable = collections.defaultdict(list)
        for i in range(len(nums)):
            if nums[i] in hashTable:
                # Compare its list
                li = hashTable[nums[i]]
                for n in li:
                    if abs(i-n) <= k:
                        return True
            hashTable[nums[i]].append(i)
        return False
        

### C++ Implementation

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> m;
        for(int i=0;i<nums.size();++i){
            if(m.find(nums[i]) != m.end() && (i-m[nums[i]])<=k){
                return true;
            }
            else{
                m[nums[i]] = i;
            }
        }
        return false;
    }
};

# 220. Contains Duplicate III (Medium)
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

### Thought 1 - Bucket sort
Maitain a hash table as length is k, iterate i belongs to one key, and check if [key-1, key, k+1] is in hash table.

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if k <= 0 or t < 0:
            return False
        hashTable = {}
        for i in range(len(nums)):
            key = nums[i] // (t+1)
            if (key in hashTable)  \
                or ((key+1) in hashTable and abs(hashTable[key+1] - nums[i]) <= t) \
                or ((key-1) in hashTable and abs(hashTable[key-1] - nums[i]) <= t): 
                return True
            if i >= k:
                if nums[(i-k)]//(t+1) in hashTable:
                    del hashTable[nums[(i-k)]//(t+1)]
            hashTable[key] = nums[i]
            
        return False

###Thought 2 - Binary Tree
But it's a bit hard to implemente in Python without special library.

https://medium.com/leetcode-%E6%BC%94%E7%AE%97%E6%B3%95%E6%95%99%E5%AD%B8/054-leetcode-219%E6%BC%94%E7%AE%97%E6%B3%95-contains-duplicate-iii-%E5%8C%85%E5%90%AB%E9%87%8D%E8%A4%87%E5%80%BC-iii-a721bd96f672