A better algorithm (than using dict) to list pairs with a given amount.

Question

Given a number, I have to figure out all the possible pairs of indices in a given array whose sum is equal to that number. I am currently using the following algorithm:

def myfunc(array,num): dic = {} for x in xrange(len(array)): # if 6 is the current key, if dic.has_key(num-array[x]): #look at whether num-x is there in dic for y in dic[num-array[x]]: #if yes, print all key-pair values print (x,y), if dic.has_key(array[x]): #check whether the current keyed value exists dic[array[x]].append(x) #if so, append the index to the list of indexes for that keyed value else: dic[array[x]] = [x] #else create a new array 

Will this be done in O(N) time? If not, what to do to do so? And in any case, is it possible to run it in O(N) without using any auxiliary data structure?

Answer 1

Will this be done in O (N) time?

Yes and no. Actually the complexity is O(N + M) , where M is the size of the output.
Unfortunately, the size of the output is in the O(N^2) worst case, for example, in the array [3,3,3,3,3,...,3] and number == 6 - this will result in a quadric number of elements to be created.

However - asymptotically - this cannot be done better than this, because it is linear in input size and output size.

Answer 2

A very simple solution that really executes O (N) times using array references. If you want to list all the output pairs, then of course (as notes), in the worst case, he should take O (N ^ 2).

 from collections import defaultdict def findpairs(arr, target): flip = defaultdict(list) for i, j in enumerate(arr): flip[j].append(i) for i, j in enumerate(arr): if target-j in flip: yield i, flip[target-j] 

Post-processing to get all output values ​​(and filter responses (i,i) ):

 def allpairs(arr, target): for i, js in findpairs(arr, target): for j in js: if i < j: yield (i, j) 

Answer 3

It may help - The optimal algorithm needed to find pairs divisible by a given integer k

(With a slight modification, we see that all pairs are divided by a given number and are not necessarily equal to a given number)