FIND TWO ELEMENTS HAVING A GIVEN DIFFERENCE | INTERVIEW BIT | PROGRAMMING | INTERVIEW | CLEAN CODE | RUBY

By: Saurav

2018-04-03 04:20:00 UTC

Given an array ‘A’ of sorted integers and another non negative integer k, find if there exists 2 indices i and j such that A[i] - A[j] = k, i != j.

Example: Input :
A : [1 3 5]
k : 4
Output : YES as 5 - 1 = 4
Return 0 / 1 ( 0 for false, 1 for true ) for this problem

Try doing this in less than linear space complexity.

InterviewBit

This problem is again among those where optimizations are what interviewer is looking for.
Note the word sorted. That usually indicates two pointers. Also, usually if a problem says find two or three, it indicates two pointer approach.

Of course we can solve the problem with two loops or a hash but lets take a look at the best one using two pointers.

How to think about it?

Fix two pointers at the start and the end. Does the function a[i]-a[j] turns in to monotonically increasing function? Nope

Then let's try fixing one at the start and other at start+1. If we do this, does the function becomes monotonic? Yes
If this problem was about addition, we would have fixed two pointers at start and end and it would have worked but here if we fix at start and start+1 and increase start+1 if the difference computed is too low. If the difference computed is too high increase the first pointer.

keep in mind that the pointers are reset when first and second points to the same index. The second is forced to move one step after.

Lest see the code with an added helper for visualization:

def diffPossible(a, b)
        return 0 if a.size < 1
        i = 1
        j = 0 
        
        while(i < a.length and j < a.length)
        
          p "#{j} #{i}"
            return 1 if i!= j and a[i]-a[j] == b
            
            if a[i]-a[j] < b 
                i+=1
            else
                j+=1
            end
        end
        return 0
end

p diffPossible([1,23,53], 12)

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)