 # Feels good to do O(n)

#1

Took me 20 mins but when the idea struck, there was no stopping. Two pointers can be really fun. I coudnt imagine doing such a question in o(n). Great question Interview bit #2

how ? can you share your approach ?

#3

My python code accepted although it has O(n) time complexity class Solution:
# @param A : list of integers
# @param B : integer
# @return an integer
def diffPossible(self, A, B):
if not len(A) or len(A)==1:
return -1
l,r=0,0
#for array dup element
if B==0:
i=0
while i<len(A)-1 and A[i]!=A[i+1]:
i+=1
if i==len(A)-1:
return -1
else:
return 1
# for unique element
while r<len(A) and l<=r:
#checking condition
if A[r]==A[l]+B:
return 1
#return (A[l],A[r])
#moving right pointer
if A[r]-A[l]<B:
r+=1
#moving left pointer
else:
l+=1
return -1

#4
``````int Solution::diffPossible(vector<int> &A, int B) {
int i,n=A.size(),j,sum;
//map<int,int> m;
i=0,j=1;
while(j<n)
{
sum=A[j]-A[i];
if(sum==B)
{
return 1;
}
if(sum>B)
{
i++;
}
else
{
j--;
}
if(i==j)
{
j++;
}
}
return 0;
``````

}
pls tell me what’s wrong.

#5

meet-hinsu take example A=1 3 5 10 and B=5 and compile with paper and pen

#6

try j++; instead of j–; and shift i==j condition on the top of loop

#7

int Solution::diffPossible(vector &A, int B)
{
int n =A.size();
if(n<2) return 0;
int i =0, j= 1;
if(B > 0) B = B* -1; //make the diff -ve because if A-B = k, then B-A = -k also exists!
while(j<n)
{
if(A[i] -A[j] == B) return 1;
else if( A[i] - A[j] > B)
{
j++;
}
else
{
if(i==j-1) j++;
i++;
}
}
return 0;
}

#8

Share the approach if thats true.