14

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..

Community
  • 1
  • 1
Imposter
  • 2,666
  • 1
  • 21
  • 31

3 Answers3

22

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • "Any set structure with O(1) setting and O(1) checking time will work instead of a hash table." can you please eloborate on the above statement.... – Imposter May 06 '12 at 11:13
  • @Imposter You need a structure that implements a semantic of a mathematical set. There are several ways to implement it - you can use a list and check if a number is there every time you add an item for O(N) efficiency, use a sorted list with a check for O(LogN), or use a hash table or an array of flags for O(1). Note that although an array of flags costs O(1) to *use*, it costs O(max(value[0..N])) to *initialize*. – Sergey Kalinichenko May 06 '12 at 11:53
6

A simple solution in O(n*Log(n)) is to sort your array and then go through your array with this function:

void find_pairs(int n, int array[], int k)
{
  int first = 0;
  int second = 0;
  while (second < n)
  {
    while (array[second] < array[first]+k)
      second++;
    if (array[second] == array[first]+k)
      printf("%d, %d\n", array[first], array[second]);
    first++;
  }
}

This solution does not use extra space unlike the solution with a hashtable.

Thomash
  • 6,339
  • 1
  • 30
  • 50
  • do we have any technique so that we dont need to sort the array ... perhaps divide and conquer technique... i dont know why ,but still i strongly believe that it can be solved using divide and conquer rule(recurssion). can you please see following program..."http://stackoverflow.com/questions/10441237/missed-logic-in-finding-sum-using-recurssion-got-segfault" i coundn't find where my logic went wrong – Imposter May 04 '12 at 15:24
  • The sort uses the divide and conquer technique. I am pretty sure that you can't do better without using extra storage. – Thomash May 04 '12 at 15:32
  • @Thomash What is the complexity of your find_pairs() function? – sleeping_dragon Feb 27 '13 at 17:12
  • @Thomash Does this work for an array with repeated ints? eg. [1 1 1 2 3] and k=0. – sleeping_dragon Feb 28 '13 at 21:00
  • this is an elegant solution plus you actually showed in code how to do it. applause – federico verchez Oct 05 '18 at 19:07
1

One thing may be done using indexing in O(n)

  • Take a boolean array arr indexed by the input list.
  • For each integer i is in the input list then set arr[i] = true
  • Traverse the entire arr from the lowest integer to the highest integer as follows:
    • whenever you find a true at ith index, note down this index.
    • see if there arr[i+k] is true. If yes then i and i+k numbers are the required pair
    • else continue with the next integer i+1
phoxis
  • 60,131
  • 14
  • 81
  • 117
  • 1
    This is not a good solution. Take the array with 2 elements: `{5, 150000}` and `k=149995`. You'll use a boolean array of size 150k for an array just two elements. – P.P May 04 '12 at 14:19
  • Agreed. The problem will depend upon the range and the distribution of the integers. Certain mapping function is needed. I think @dasblinkenlight's hash solution is better. – phoxis May 04 '12 at 14:22
  • 1
    @KingsIndian I wouldn't necessarily dismiss this solution as "not good": if you have a lot of memory anyway, there is no excuse to refrain from using it if it can help you speed up your calculation: when the number of items is high and the largest item is relatively small, this solution beats hash tables on speed hands down! Of course you need good judgement when you make a choice like that, but "memory for speed" tradeoff sounds like a no-brainer these days :) – Sergey Kalinichenko May 04 '12 at 14:28
  • @dasblinkenlight, Even if you havee infinite memory, setting `true/false` for a mega boolean array when the no. of elements(150K in my example) are too few is *very very* inefficient. There's no "memory for speed" trade-off here. Both are getting worse in this method. – P.P May 04 '12 at 14:32
  • If the range is small (e.g. 8-bit integers), then this method would probably find the answer faster than you could create a hash table and consume less space. – Brendan May 04 '12 at 14:36
  • @KingsIndian I agree - that's why I mentioned good judgement: essentially, this approach converts the problem from O(n) to O(max(numbers)) and a much smaller constant factor, so figuring out what's cheaper is a tricky "juggling act". – Sergey Kalinichenko May 04 '12 at 14:37
  • 2
    @dasblinkenlight That's why I didn't downvote but commented on the flaws.Becuase, I accept this is still a *valid* solution. :) – P.P May 04 '12 at 14:39