Python Sum of Pairs Codewars Solution requires optimization

Question

Sum of Pairs

Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.

sum_pairs([11, 3, 7, 5], 10)
# ^--^ 3 + 7 = 10
== [3, 7]
sum_pairs([4, 3, 2, 3, 4], 6)
# ^-----^ 4 + 2 = 6, indices: 0, 2 *
# ^-----^ 3 + 3 = 6, indices: 1, 3
# ^-----^ 2 + 4 = 6, indices: 2, 4
# * entire pair is earlier, and therefore is the correct answer
== [4, 2]
sum_pairs([0, 0, -2, 3], 2)
# there are no pairs of values that can be added to produce 2.
== None/nil/undefined (Based on the language)
sum_pairs([10, 5, 2, 3, 7, 5], 10)
# ^-----------^ 5 + 5 = 10, indices: 1, 5
# ^--^ 3 + 7 = 10, indices: 3, 4 *
# * entire pair is earlier, and therefore is the correct answer
== [3, 7]
Negative numbers and duplicate numbers can and will appear.
NOTE: There will also be lists tested of lengths upwards of 10,000,000 elements. Be sure your code doesn't time out.

def sum_pairs(ints, s):
 '''
 Params:
 ints: list[int]
 s: int --- sum
 Return
 First two values from left in ints that add up to form sum
 '''
 ints_dict = {k:v for v,k in enumerate(ints)} # O(n)
 earliest_ending_idx = float('inf')
 earliest_pair = None
 for idx, num in enumerate(ints): # O(n)
 if idx >= earliest_ending_idx:
 return earliest_pair
 try:
 second_num_idx = ints_dict[s-num]
 if second_num_idx != idx:
 if max(second_num_idx, idx) < earliest_ending_idx:
 earliest_ending_idx = max(second_num_idx, idx)
 earliest_pair = [num, s-num]
 except KeyError:
 # s-num not in dict
 pass
 return earliest_pair

It seems to me that my code is O(n) in time complexity but I can't submit the solution since it took too long to run. Am I mistaken in my analysis and is there a better way to solve this problem?

• pacmaninbw: Welcome to the Code Review Community. Please provide the programming challenge description in the question. If we don't have an idea of what the code is supposed to do, we really can't review the code.
• Reinderien: Rather than pasting a screenshot of the problem statement, please paste a quoted > text block verbatim. Otherwise this is not searchable.

Answer 1

You have the right idea with storing the complements, i.e. s-num.

However, there's no need to store indices. The iteration can be stopped when a pair is found, so iterating through the list in the usual manner will yield the first such pair.

def sum_pairs(ints, s):
 complement_dict = {}
 
 for i in ints:
 if i in complement_dict:
 return [s-i, i]
 else:
 complement_dict[s - i] = i
 return None

Answer 2

your solution first maps all of the numbers, and then check for pairs.

what if, for instance, the list of numbers is very long, and the first two items already sum up to the desired sum?

I think that the optimal solution would iterate over the list only once.

• IceTea: This is a good prompt! Unfortunately when I saw this, I was still stuck with the initial solution I had and didn't consider the (on hindsight) obvious option of storing complements in the dictionary as I go.