# Containing Duplicated III

Sep 4th, 2020
1,455
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution {
2.     public:
3.         bool containsNearbyAlmostDuplicate(vector <int> & nums, int k, int t) {
4.             if(nums.empty() || k==0 || t<0)    return false;
5.             multiset<long long> kWindow;
6.             // if lower_bound and upper_bound are not found it returns set.end()
7.
8.             for (long long i = 0; (i <= k && i<nums.size() ); i++) {
9.                 if (!kWindow.empty()) {
10.                     long long curr = nums[i];
11.                     auto it1 = kWindow.upper_bound(curr);
12.                     auto it2 = kWindow.lower_bound(curr);
13.                     auto itTemp = prev(it2, 1);
14.
15.                     // cout << "Set elements: ";
16.                     // for(auto &x: kWindow)   cout << x << " ";
17.                     // cout << endl;
18.                     // cout << "Element coming: " << curr << endl;
19.                     // cout << "Upper bound: " << *it1 << endl;
20.                     // cout << "Lower bound: " << *it2 << endl;
21.                     // //cout << "prevLowerBound: " << *itTemp << endl;
22.                     // cout << "Upper bound is not present: " << (it1==kWindow.end()) << endl;
23.                     // cout << "Lower bound is not present: " << (it2==kWindow.end()) << endl;
24.                     // cout << "Is lower bound the beginning: " << (it2==kWindow.begin()) << endl;
25.                     // cout << " ============= " << endl;
26.                     if ( (it2!=kWindow.end() && *it2==curr) || (it2!=kWindow.end() && it2!=kWindow.begin() && curr-*itTemp<=t) || (it1!=kWindow.end() && *it1-curr<=t) || ( abs((long long)(*(kWindow.rbegin())-curr)) <=t) ) {
27.                         cout <<  abs(*(kWindow.rbegin())-curr) << endl;
28.                         return true;
29.                     }
30.                     kWindow.insert(curr);
31.                 } else {
32.                     kWindow.insert(nums[i]);
33.                 }
34.             }
35.
36.             for (long long i = k+1; i < nums.size(); i++) {
37.                 //oldest element is i-k
38.                 long long toDelete = nums[i - k - 1];
39.                 auto itr = kWindow.find(toDelete);
40.                 kWindow.erase(itr);
41.
42.                 long long curr = nums[i];
43.                 auto it1 = kWindow.upper_bound(curr);
44.                 auto it2 = kWindow.lower_bound(curr);
45.                 auto itTemp = prev(it2, 1);
46.
47.                 //cout << "Set elements: ";
48.                 //for(auto &x: kWindow)   cout << x << " ";
49.                 // cout << endl;
50.                 // cout << "Element coming: " << curr << endl;
51.                 // cout << "Upper bound: " << *it1 << endl;
52.                 // cout << "Lower bound: " << *it2 << endl;
53.                 // //cout << "prevLowerBound: " << *itTemp << endl;
54.                 // cout << "Upper bound is not present: " << (it1==kWindow.end()) << endl;
55.                 // cout << "Lower bound is not present: " << (it2==kWindow.end()) << endl;
56.                 // cout << "Is lower bound the beginning: " << (it2==kWindow.begin()) << endl;
57.                 // cout << " ============= " << endl << endl;
58.
59.                 if ((it2!=kWindow.end() && *it2==curr) || (it2!=kWindow.end() && it2!=kWindow.begin() && curr-*itTemp<=t) || (it1!=kWindow.end() && *it1-curr<=t) || ( abs((long long)(*(kWindow.rbegin())-curr)) <=t) ) {
60.                     return true;
61.                 }
62.                 kWindow.insert(curr);
63.             }
64.
65.             return false;
66.
67.         }
68. };