Given an array, find whether there are 2 numbers whose difference is c

Question

I have an O(n²) solution to this problem and wondering whether there is a better solution. If we were trying to find 2 numbers, whose sum is c, then i know that there is an O(nlogn) solution. (given here) I try the similar approach here: i first sort the array using mergesort in O(nlogn) time, then i start from both ends of the array, and look at their differences. If this is equal to c, then we are done. If difference is bigger than c, then i decrease the rightmost index by 1, but i think this is wrong, we cannot know whether we have do decrease the rightmost index or we have to increase the leftmost index. Am i right? Can we solve this problem in a better time complexity? Thanks

Answer 1

They key is that once the array is sorted, binary search is only O(logn).

For each number x in the array, test whether x-c is in the array via binary search. This is still O(nlogn).

If you want to be fancy, you can do it by only iterating twice through the array, but the complexity is dominated by the sorting step anyway.

Answer 2

My Approach, using hash and no need for pre-sorting, It depends on the hash implementation, In the Best Case it can be done in O(n), In the worst case O(nlogn),

arr[] = { ... }
hash[] // maps Integer to Boolean
for e in arr:
    hash[e] = true
    if hash[e+c] == true Or hash[e-c] == true:
        return true
return false

Iterating over the array, for each element e do:

• map e to true in the hash
• if there are element with difference of c to the current element, then Bingo :D

Hope this helps :)

Answer 3

You can sort the array which, takes O(n log n) time. Then you can create a second array by replacing each member x in the first with c - x, and then reversing. Then, you can see if the two arrays have an element in commonwhich takes two traversals for O(n) each.