LeetCode Q220: Contains Duplicate III

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

Solution:
Keep tracking the past k elements by forming a BST for these k numbers. When new element coming, search BST to see if a target number exist. Remove the furthest element out of BST and insert current element to BST. 

Here, we need to use some nice features provided by STL. In STL, a BST is implemented as a "set". In set, there exist a functionality that can search the smallest number that is greater than search key. by using this feature, we can determine if there exist a number that is in the range of [key-t, key+t].:

	class Solution {
	public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
	set<int> mySet;
	for(int i=0; i<nums.size(); i++){
	// remove element outside k distance range from mySet
	if(i-k-1>=0)
	mySet.erase(nums[i-k-1]);
	set<int>::iterator itup = mySet.upper_bound(nums[i]-t-1);
	if(itup==mySet.end()){
	mySet.insert(nums[i]);
	continue;
	}
	if(abs(*itup-nums[i])<=t )
	return true;
	mySet.insert(nums[i]);
	}
	return false;
	}
	};

view raw Q220ContainsDuplicateIII.cpp hosted with ❤ by GitHub