Return to Answer

• Your code contains a few lines that accomplish nothing and obfuscate your intent:

        else: 
            continue
  

  If the conditional is false, you'll automatically continue on to the next iteration without having to tell the program to do that.

        return None
  

  All Python functions implicitly return None; however, PEP 8 recommends this practice.

• num_lst = list(range(len(nums))) effectively generates a list of all the indices in the nums input list. Then, you immediately enumerate this list, which produces pairs of identical indices indx, num. If all you're attempting to do is iterate, this is significant obfuscation; simply call enumerate directly on nums 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 and num_lst are confusing variable names, especially when they're all actually indices (which are technically numbers).

• Your code contains a few lines that accomplish nothing and obfuscate your intent:

        else: 
            continue
  

  If the conditional is false, you'll automatically continue on to the next iteration without having to tell the program to do that.

        return None
  

  All Python functions implicitly return None. While PEP 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 the nums input list. Then, you immediately enumerate this list, which produces pairs of identical indices indx, num. If all you're attempting to do is iterate, this is significant obfuscation; simply call enumerate directly on nums 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 and num_lst are confusing variable names, especially when they're all actually indices (which are technically numbers).

• Your code contains a few lines that accomplish nothing and obfuscate your intent:

        else: 
            continue
  

  If the conditional is false, you'll automatically continue on the next iteration without having to tell the program to do that.

        return None
  

  All Python functions implicitly return None; however, PEP 8 recommends this practice.

• num_lst = list(range(len(nums))) effectively generates a list of all the indices in the nums input list. Then, you immediately enumerate this list, which produces pairs of identical indices indx, num. If all you're attempting to do is iterate, this is significant obfuscation; simply call enumerate directly on nums 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 and num_lst are confusing variable names, especially when they're all actually indices (which are technically numbers).

• Your code contains a few lines that accomplish nothing and obfuscate your intent:

        else: 
            continue
  

  If the conditional is false, you'll automatically continue on to the next iteration without having to tell the program to do that.

        return None
  

  All Python functions implicitly return None; however, PEP 8 recommends this practice.

• num_lst = list(range(len(nums))) effectively generates a list of all the indices in the nums input list. Then, you immediately enumerate this list, which produces pairs of identical indices indx, num. If all you're attempting to do is iterate, this is significant obfuscation; simply call enumerate directly on nums 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 and num_lst are confusing variable names, especially when they're all actually indices (which are technically numbers).

• This code is inefficient, running in quadratic time, or O(n²). 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 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 of hashing. The dictionary hist offers constant O(1) lookup time. Whenever we visit a new element in nums, we check to see if its sum complement is in the dictionary; else, we store it in the dictionary as a num => 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 O(1) space and 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. Sort nums.
  2. Create two pointers representing an index at 0 and an index at len(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.

• This code is inefficient, running in quadratic 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 of hashing. The dictionary hist offers constant \$\mathcal{O}(1)\$ lookup time. Whenever we visit a new element in nums, we check to see if its sum complement is in the dictionary; else, we store it in the dictionary as a num => 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. Sort nums.
  2. Create two pointers representing an index at 0 and an index at len(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 try 3 Sum!