Simple and easy to understand C++ O(n) sol with unordered map


#1
int Solution::diffPossible(const vector<int> &A, int B) {
int n=A.size();
if(n<2) return 0;
unordered_set<int> set;
for(int i=0;i<n;i++){
    if(set.find(A[i]) != set.end()) return 1;
    if(A[i]>=B)  set.insert(A[i]-B);
    else        set.insert(B+A[i]);
}
return 0;

}


#2

Its not o(n) solution because set::find takes o(log n) to search for an individual element. That’s why it is o(nlogn) solution.


#3

i think it still not a O(nlogn) solution as unordered map search in O(n) in worst case ,so it will be O(n^2) solution …