Two solutions || with and without hash


#1

Without Hash: Time Complexity O(nlogn) and space complexity O(1).

int Solution::diffPossible(const vector &A, int B) {
vector C=A;
sort(C.begin(),C.end());
int i=0,j=1,diff=0;
while(i<j &&j<C.size())
{
diff=C[j]-C[i];
if(diff<B)
{
j++;
}
if(diff>B)
{
i++;
}
if(diff==B)
{
return 1;
}
}
return 0;
}

WITH HASH. Time complexity O(n) Space Complexity O(n).
int Solution::diffPossible(const vector &A, int B) {

unordered_map<int,int> hash;
int n=A.size();
for(int i=0;i<n;i++)
{
if(hash.find(B+A[i])!=hash.end() || hash.find(A[i]-B)!=hash.end())
{
return 1;
}
else
{
hash[A[i]]=1;
}
}
return 0;
}