Python 3 two-sum performance

Question

I just submitted a Python solution to the 'Two Sum' problem on LeetCode.

The Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9

Because nums[0] + nums[1] = 2 + 7 = 9

return [0, 1].

My Solution

class Solution:
 def twoSum(self, nums, target):
 number_bonds = {}
 for index, value in enumerate(nums):
 if value in number_bonds:
 return [number_bonds[value], index]
 number_bonds[target - value] = index
 return None

It was accepted and then told me the following:

Your runtime beats 83.12 % of python3 submissions.

This means that 16.88% of python3 submissions were more efficient than this one.

How can I get this more efficient than the solution provided above? Is there a funky way to do this with numpy that I'm not getting? Is there maybe another data structure I should use in this situation? Or a better algorithm altogether? I've explored a few alternate solutions and profiled with timeit but none were faster than this.

• FreezePhoenix: Why the unnecessary class? Is that part of the challenge?
• janos: @FreezePhoenix yes, it is part of the challenge
• janos: I was curious of the variation of submission times. So I submitted the exact same code as Python3, and it said it beats 100% of python3 submissions! (I've never actually seen such good performance on leetcode.) In any case, you have a passing solution, and trying to further optimize this solution won't be very fruitful. I suggest to read the part of this answer after the line "Donald Knuth said:".
• PragmaticProgrammer: @janos I agree with your point about premature optimisation, however I don't think it's relevant here. I posed this question to further my understanding and this is not production code.

Answer 1

I think your solution is already pretty good. It is at worst \$\mathcal{O}(n)\$ in both runtime and memory. You use enumerate instead of iterating over the indicies manually.

The only four things I would comment on are:

1. In real life code, this being a class would of course be completely unnecessary (but it seems to be mandatory in this case).
2. Explicitly returning None at the end. This is always a judgement call between being unnecessarily verbose (since it is returned implicitly anyways) and being more expressive. Since this case is explicitly excluded in the problem description (all inputs have exactly one solution), I would not add it here. If it were an explicit rule to return None in case there was no solution I would, however, include it.
3. You should add some docstring to the class/method. At least to get in the habit of always doing it.
4. Python's official style-guide, PEP8, recommends using lower_case for variable, function and method names (but this seems to also be mandatory from the problem description).

Answer 2

Your solution is pretty much optimized using Python constructs. If you want to gain speed, you'd have to loop in C rather than in Python. This is possible by using the following code:

class Solution:
 def twoSum(self, numbers, target):
 bounds = {target - value: index for index, value in enumerate(numbers)}
 return next(((index, bounds[value]) for index, value in enumerate(numbers) if value in bounds), None)

But this solution has the drawback to always iterate at least once over the whole input, meaning it is \$\mathcal{O}(n)\$ best case; whereas your solution is \$\mathcal{O}(n)\$ worst case and \$\mathcal{O}(1)\$ best case. So this solution should be slower when the answer couple is near the beginning of the array.

• mathandy: This won't work in all cases, e.g. if the first number is half the target, it'll return [0,0]. A quick fix is return next(((index, i2) for index, value in enumerate(numbers) if value in bounds and (i2 := bounds[value]) != index), None)
• 301_Moved_Permanently: Walrus operator makes this so nice!