Leetcode Two Sum code in Python

Question 1

Here's my solution for the LeetCode's Two Sum problem.

Problem:

Given an array of integers, return indices of the two numbers suchthat they add up to a specific target.
You may assume that each input would have exactly one solution, andyou may not use the same element twice.
Example:
Givennums = [2, 7, 11, 15], target = 9
Becausenums[0] + nums[1] = 2 + 7 = 9,return [0, 1]

My solution:

def twoSum(nums, target):    """    :type nums: List[int]    :type target: int    :rtype: List[int]    """    num_lst = list(range(len(nums)))    for indx, num in enumerate(num_lst):        for num_other in num_lst[indx+1:]:            if nums[num] + nums[num_other] == target:                return [num, num_other]            else:                 continue    return None

I would love feedback on code efficiency and style/formatting.

Question 2

Would any of the lists contain negative numbers?

Question 3

@MSeifert I don't know, but feel free to assume yes

Question 4

Code Style

Your code contains a few lines that accomplish nothing and obfuscate your intent:
```
    else:         continue
```
If the conditional is false, you'll automaticallycontinue on to the next iteration without having to tell the program to do that.
```
    return None
```
All Python functions implicitlyreturn None. WhilePEP 8 appears to endorse this practice ("explicit is better than implicit"), it seems noisy to me.
num_lst = list(range(len(nums))) effectively generates a list of all the indices in thenums input list. Then, you immediatelyenumerate this list, which produces pairs of identical indicesindx, num. If all you're attempting to do is iterate, this is significant obfuscation; simply callenumerate directly onnums to produce index-element tuples:
```
def twoSum(self, nums, target):    for i, num in enumerate(nums):        for j in range(i + 1, len(nums)):            if num + nums[j] == target:                return [i, j]
```
This makes the intent much clearer: there are no duplicate variables with different names representing the same thing. It also saves unnecessary space and overhead associated with creating a list from a range.
Following on the previous item,indx, num andnum_lst are confusing variable names, especially when they're all actually indices (which are technically numbers).

Efficiency

This code is inefficient, running inquadratic time, or\$\mathcal{O}(n^2)\$. Leetcode is generous to let this pass (but won't be so forgiving in the future!). The reason for this is the nested loop; for every element in your list, you iterate over every other element to draw comparisons. A linear solution should finish in ~65 ms, while this takes ~4400 ms.
Here is an efficient solution that runs in\$\mathcal{O}(n)\$ time:
```
hist = {}for i, n in enumerate(nums):    if target - n in hist:        return [hist[target-n], i]    hist[n] = i
```
How does this work? The magic ofhashing. The dictionaryhist offers constant\$\mathcal{O}(1)\$ lookup time. Whenever we visit a new element innums, we check to see if its sum complement is in the dictionary; else, we store it in the dictionary as anum => index pair.
This is the classic time-space tradeoff: the quadratic solution is slow but space efficient, while this solution takes more space but gains a huge boost in speed. In almost every case, choose speed over space.
For completeness, even if you were in a space-constrained environment, there is a fast solution that uses\$\mathcal{O}(1)\$ space and\$\mathcal{O}(n\log{}n)\$ time. This solution is worth knowing about for the practicality of the technique and the fact that it's a common interview follow-up. The way it works is:
1. Sortnums.
2. Create two pointers representing an index at 0 and an index atlen(nums) - 1.
3. Sum the elements at the pointers.
  - If they produce the desired sum, return the pointer indices.
  - Otherwise, if the sum is less than the target, increment the left pointer
  - Otherwise, decrement the right pointer.
4. Go back to step 3 unless the pointers are pointing to the same element, in which case return failure.
Be wary of list slicing; it's often a hidden linear performance hit. Removing this slice as the nested loop code above illustrates doesn't improve the quadratic time complexity, but it does reduce overhead.

Now you're ready to try3 Sum!

Question 5

As for returningNone, seethe relevant section of PEP 8.

Question 6

That's true, Python does say "explicit is better than implicit". I can amend my recommendation to be "at least be aware that Python statements implicitlyreturn None". Maybe Python should also putelse: continue at the end of every loop, just to be explicit :-)

Question 7

Python should, butdoesn't know not to copy the entire thing. It has no such optimisation.

Question 8

@wizzwizz4 No lazy copying? E.g. return a pointer in O(1) to the slice element and then wait for mutation to perform a copy? I'd like to update if incorrect here.

Question 9

@ggorlen Apparently not.Try it online! Rule of thumb: Python performsno optimisations at all.

Question 10

num_lst = list(range(len(nums)))for indx, num in enumerate(num_lst):

I'm not sure if I'm missing something, but I think not. I ran this code

nums = [2,5,7,9]num_lst = list(range(len(nums)))list(enumerate(num_lst))output : [(0, 0), (1, 1), (2, 2), (3, 3)]

So why do you create the list and then enumerate it? Maybe what you want to do is simply :enumerate(nums) thenenumerate(nums[index+1:]) on your other loop? A simpler way would be to only use the ranges, as I'll show below.

Also, given your input, there's a possibility that a single number would be higher than the target, in this case you shouldn't make the second iteration.

You also don't need theelse: continue , as it's going tocontinue either way.

I'd end up with :

def twoSum(nums, target):    """    :type nums: List[int]    :type target: int    :rtype: List[int]    """    for i1 in range(len(nums)):        if nums[i1] > target:            continue        for i2 in range(i1 + 1, len(nums)):            if nums[i1] + nums[i2] == target:                return [i1, i2]    return None

Without knowing the expected input size, it's hard to focus on performance improvements. The main goal of my review was to remove what seemed like a misunderstanding in your code and in my opinion the code is clearer now.

Question 11

Your code is stillO(n**2), so I wouldn't say it offers any significant performance boost.

Question 12

Also, your code has a few bugs. It doesn't work with negative numbers, it doesn't even work with0 reliably (twoSum([2,0], 2)) and it uses the same number twice (twoSum([1, 1], 2)). :-/

Question 13

@EricDuminil The latter is fine; number != element.

Question 14

@wizzwizz4: Thanks for the comment. You're right. I meant to writetwoSum([1], 2), which should returnNone, not[0, 0]. The bug is here, my description was incorrect.

Question 15

@EricDuminil I mainly wanted to focus on some of the bloat to simplify it, went fast and introduced bugs, lol. And without the expected size of input it's hard to tell if there's a real performance value to my answer (and to any other one at that, if we always expect 4 numbers, performance isn't really an issue). I also wrongfully assumed that we dealt with positive non-zero integers.

Question 16

You can useitertools.combinations for a more readable (and likely faster)for loop. As long as returning alist isn't a requirement, I would consider it better style to return atuple instead. (Especially since it allows you to convey the list length.) Also, as long as the current name isn't a requirement,it is preferable to usesnake_case for function and variable names.

from itertools import combinationsdef twoSum(nums, target):    """    :type nums: List[int]    :type target: int    :rtype: List[int]    """    for (i, first), (j, second) in combinations(enumerate(nums), 2):        if first + second == target:            return [i, j]    return None

Question 17

You don't need to createnum_list anymore. Also,combinations requires (at least in Python 3.6) a second argumentr which specifies the length of the combinations. Here,r should be 2.

ggorlen 4,1972 gold badges19 silver badges28 bronze badges · Answer 1 · 2019-10-13 04:37:59Z

Code Style

Your code contains a few lines that accomplish nothing and obfuscate your intent:
```
    else:         continue
```
If the conditional is false, you'll automaticallycontinue on to the next iteration without having to tell the program to do that.
```
    return None
```
All Python functions implicitlyreturn None. WhilePEP 8 appears to endorse this practice ("explicit is better than implicit"), it seems noisy to me.
num_lst = list(range(len(nums))) effectively generates a list of all the indices in thenums input list. Then, you immediatelyenumerate this list, which produces pairs of identical indicesindx, num. If all you're attempting to do is iterate, this is significant obfuscation; simply callenumerate directly onnums to produce index-element tuples:
```
def twoSum(self, nums, target):    for i, num in enumerate(nums):        for j in range(i + 1, len(nums)):            if num + nums[j] == target:                return [i, j]
```
This makes the intent much clearer: there are no duplicate variables with different names representing the same thing. It also saves unnecessary space and overhead associated with creating a list from a range.
Following on the previous item,indx, num andnum_lst are confusing variable names, especially when they're all actually indices (which are technically numbers).

Efficiency

This code is inefficient, running inquadratic time, or\$\mathcal{O}(n^2)\$. Leetcode is generous to let this pass (but won't be so forgiving in the future!). The reason for this is the nested loop; for every element in your list, you iterate over every other element to draw comparisons. A linear solution should finish in ~65 ms, while this takes ~4400 ms.
Here is an efficient solution that runs in\$\mathcal{O}(n)\$ time:
```
hist = {}for i, n in enumerate(nums):    if target - n in hist:        return [hist[target-n], i]    hist[n] = i
```
How does this work? The magic ofhashing. The dictionaryhist offers constant\$\mathcal{O}(1)\$ lookup time. Whenever we visit a new element innums, we check to see if its sum complement is in the dictionary; else, we store it in the dictionary as anum => index pair.
This is the classic time-space tradeoff: the quadratic solution is slow but space efficient, while this solution takes more space but gains a huge boost in speed. In almost every case, choose speed over space.
For completeness, even if you were in a space-constrained environment, there is a fast solution that uses\$\mathcal{O}(1)\$ space and\$\mathcal{O}(n\log{}n)\$ time. This solution is worth knowing about for the practicality of the technique and the fact that it's a common interview follow-up. The way it works is:
1. Sortnums.
2. Create two pointers representing an index at 0 and an index atlen(nums) - 1.
3. Sum the elements at the pointers.
  - If they produce the desired sum, return the pointer indices.
  - Otherwise, if the sum is less than the target, increment the left pointer
  - Otherwise, decrement the right pointer.
4. Go back to step 3 unless the pointers are pointing to the same element, in which case return failure.
Be wary of list slicing; it's often a hidden linear performance hit. Removing this slice as the nested loop code above illustrates doesn't improve the quadratic time complexity, but it does reduce overhead.

Now you're ready to try3 Sum!

That's true, Python does say "explicit is better than implicit". I can amend my recommendation to be "at least be aware that Python statements implicitlyreturn None". Maybe Python should also putelse: continue at the end of every loop, just to be explicit :-)
Python should, butdoesn't know not to copy the entire thing. It has no such optimisation.
@wizzwizz4 No lazy copying? E.g. return a pointer in O(1) to the slice element and then wait for mutation to perform a copy? I'd like to update if incorrect here.
@ggorlen Apparently not.Try it online! Rule of thumb: Python performsno optimisations at all.

IEatBagels 12.7k3 gold badges48 silver badges99 bronze badges · Answer 2 · 2019-01-29 19:24:43Z

num_lst = list(range(len(nums)))for indx, num in enumerate(num_lst):

I'm not sure if I'm missing something, but I think not. I ran this code

nums = [2,5,7,9]num_lst = list(range(len(nums)))list(enumerate(num_lst))output : [(0, 0), (1, 1), (2, 2), (3, 3)]

So why do you create the list and then enumerate it? Maybe what you want to do is simply :enumerate(nums) thenenumerate(nums[index+1:]) on your other loop? A simpler way would be to only use the ranges, as I'll show below.

Also, given your input, there's a possibility that a single number would be higher than the target, in this case you shouldn't make the second iteration.

You also don't need theelse: continue , as it's going tocontinue either way.

I'd end up with :

def twoSum(nums, target):    """    :type nums: List[int]    :type target: int    :rtype: List[int]    """    for i1 in range(len(nums)):        if nums[i1] > target:            continue        for i2 in range(i1 + 1, len(nums)):            if nums[i1] + nums[i2] == target:                return [i1, i2]    return None

Without knowing the expected input size, it's hard to focus on performance improvements. The main goal of my review was to remove what seemed like a misunderstanding in your code and in my opinion the code is clearer now.

Your code is stillO(n**2), so I wouldn't say it offers any significant performance boost.
Also, your code has a few bugs. It doesn't work with negative numbers, it doesn't even work with0 reliably (twoSum([2,0], 2)) and it uses the same number twice (twoSum([1, 1], 2)). :-/
@wizzwizz4: Thanks for the comment. You're right. I meant to writetwoSum([1], 2), which should returnNone, not[0, 0]. The bug is here, my description was incorrect.
@EricDuminil I mainly wanted to focus on some of the bloat to simplify it, went fast and introduced bugs, lol. And without the expected size of input it's hard to tell if there's a real performance value to my answer (and to any other one at that, if we always expect 4 numbers, performance isn't really an issue). I also wrongfully assumed that we dealt with positive non-zero integers.

Solomon Ucko 1,5761 gold badge10 silver badges17 bronze badges · Answer 3 · 2019-01-26 15:03:26Z

You can useitertools.combinations for a more readable (and likely faster)for loop. As long as returning alist isn't a requirement, I would consider it better style to return atuple instead. (Especially since it allows you to convey the list length.) Also, as long as the current name isn't a requirement,it is preferable to usesnake_case for function and variable names.

from itertools import combinationsdef twoSum(nums, target):    """    :type nums: List[int]    :type target: int    :rtype: List[int]    """    for (i, first), (j, second) in combinations(enumerate(nums), 2):        if first + second == target:            return [i, j]    return None

You don't need to createnum_list anymore. Also,combinations requires (at least in Python 3.6) a second argumentr which specifies the length of the combinations. Here,r should be 2.

Movatterモバイル変換

Stack Exchange Network

Leetcode Two Sum code in Python

3 Answers3

Code Style

Efficiency

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS