Find numbers having a particular difference within a sorted list

Question

Given N sorted numbers, we need to find, if there exists a pair, with difference K.

A O(N log N) solution is to check for every number x , check if (x + K) exists using binary search.

I was wondering if there is a better, O(n)time, and O(1) space solution for it.

Answer 1

Given the list is sorted, you can run two pointers through the list in O(n) time. Basically something along the lines of:

index1 = 0
index2 = 0
while index2 < size(array):
    if array[index2] - array[index1] == K:
        print both numbers and exit
    if array[index2] - array[index1] < K:
        index2++;
    else
        index1++;

In other words, if the difference between the numbers is too low, increase the higher number (make difference larger), otherwise increase the lower number (make difference smaller).

You can see this in action with the following Python program:

lst = [1,2,3,4,5,6,7,50,100,120,121,122,123,130,199,299,399]
diff = 7
ix1 = 0
ix2 = 0
while ix2 < len (lst):
    print "Comparing [%d]=%d against [%d]=%d"%(ix1,lst[ix1],ix2,lst[ix2])
    if lst[ix2] - lst[ix1] == diff:
        print lst[ix1], lst[ix2]
        break
    if lst[ix2] - lst[ix1] < diff:
        ix2 = ix2 + 1
    else:
        ix1 = ix1 + 1

which outputs:

Comparing [0]=1 against [0]=1
Comparing [0]=1 against [1]=2
Comparing [0]=1 against [2]=3
Comparing [0]=1 against [3]=4
Comparing [0]=1 against [4]=5
Comparing [0]=1 against [5]=6
Comparing [0]=1 against [6]=7
Comparing [0]=1 against [7]=50
Comparing [1]=2 against [7]=50
Comparing [2]=3 against [7]=50
Comparing [3]=4 against [7]=50
Comparing [4]=5 against [7]=50
Comparing [5]=6 against [7]=50
Comparing [6]=7 against [7]=50
Comparing [7]=50 against [7]=50
Comparing [7]=50 against [8]=100
Comparing [8]=100 against [8]=100
Comparing [8]=100 against [9]=120
Comparing [9]=120 against [9]=120
Comparing [9]=120 against [10]=121
Comparing [9]=120 against [11]=122
Comparing [9]=120 against [12]=123
Comparing [9]=120 against [13]=130
Comparing [10]=121 against [13]=130
Comparing [11]=122 against [13]=130
Comparing [12]=123 against [13]=130
123 130