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 :slight_smile:


#2

how ? can you share your approach ?


#3

My python code accepted although it has O(n) time complexity :sweat_smile:
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[4]=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.