find pair of numbers whose difference is an input value 'k' in an unsorted array
algorithm, arrays, c, performance
Solution
You can do it in O(n) with a hash table. Put all numbers in the hash for O(n), then go through them all again looking for `number[i]+k`. Hash table returns "Yes" or "No" in O(1), and you need to go through all numbers, so the total is O(n). Any set structure with O(1) setting and O(1) checking time will work instead of a hash table.
Problem
As mentioned in the title, I want to find the pairs of elements whose difference is K ``` example k=4 and a[]={7 ,6 23,19,10,11,9,3,15} output should be : 7,11 7,3 6,10 19,23 15,19 15,11 ``` I have read the previous posts in SO " find pair of numbers in array that add to given sum" In order to find an efficient solution, how much time does it take? Is the time complexity `O(nlogn)` or `O(n)`? I tried to do this by a divide and conquer technique, but i'm not getting any clue of exit condition... If an efficient solution includes sorting the input array and manipulating elements using two pointers, then I think I should take minimum of `O(nlogn)`... Is there any math related technique which brings solution in `O(n)`. Any help is appreciated..