Advertisement
HjHimansh

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. };
Advertisement
RAW Paste Data Copied
Advertisement