trjhtr

I gave this one a shot, and the code works. Am I on the right track? How can the code be improved? Also, I am unaware of how to determine if this would be linear time or not. Could someone maybe break that determination down for me?

'''
Problem statement: Find pairs in an integer array whose sum is equal to n (bonus: do it in linear time)

@author: Anonymous3.1415
'''

def pair_sum_to_n(integer_list, n):
 pairs = 
 #checks for the occurence of halfs
 if not n % 2:
 if integer_list.count(n/2) > 1:
 pairs.append((n/2, n/2))
 integer_set = set(integer_list) - n/2
 #finds pairs of integers where x + (n - x) = n
 for x in integer_set:
 if (n - x) in integer_set:
 if (n - x, x) not in pairs:
 pairs.append((x, n - x))
 return pairs

integer_list = list(map(int, raw_input().strip().split(" ")))
pairs = pair_sum_to_n(integer_list, 10)
print(pairs)

Problem definition

it is not clearly defined whether pair_sum_to_n([1, 9, 9, 1, 9], 10) shall result in. your implementation suggests (1, 9) as desired result. other possibilites include

• (1, 9)


• (9, 1)


• (9, 1), (1, 9)


• [(1, 9), (1, 9)]


• [(1, 9), (9, 1)]


• [(9, 1), (1, 9)]


• [(1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9)]


• ...

Indentation

integer_set is not defined for odd n

Special case handling n/2for even n

always prove it is necessary/useful to do extra code. the best implementation (given that it matches the requirements) is the one that is most easy to understand, implement and test. your special looks like a fine shortcut but requires extra testing odd/even. the indentation error would probably not be there when this case had been omitted. however it is needed as you copy all values from the parameter to a set.

Parameter name integer_list

this suggests the imput parameter is a list. however your algorithm could work on every iterable (if you omit the special case) so a name like integers or values would be less suggestive.

Copy iterable to set

this is a good strategy if the operations beeing performed on the values lateron are expensive and the values are expected to contain many duplicates. if one of these conditions is false - don't do it. as your test is quite cheap (the set containment check is more or less the same as an insert to a set), you could omit all that special case handling and iterate over the parameter once. however if you work on an iterable with duplicates you have to sort out duplicate pairs by using a set as storage for the sorted pairs. also if you avoid the filtering on the input you could adapt to different problem definitions (see problem definition above) easily.

The map by default returns a list. You do not need another wrapper around it.

Your current implementation is of $ O(n^2) $ complexity. The statement:

(n - x, x) not in pairs

is of $ O(n) $ time, which lies inside a loop with $ O(n) $.

To do this in linear time, generate a dict/hash where you store simply the $ n - x $ values in first iteration. In the second (and independent) iteration, simply append the pair $$ left( min(x, n - x), max(x, n - x) right) $$ for each x in your list, if the $ O(1) $ lookup in the dict is true.