I try the most to solve a twoSum problem in leetcode

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.


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

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

The plan:

  1. brute force to iterate len(nums) O(n)
  2. search for target - num[i] with a hash table O(1)


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_d = {}
        for i in range(len(nums)):
            nums_d.setdefault(nums[i], []).append(i)

        for i in range(len(nums)):
            sub_target = target - nums[i]
            nums_d[nums[i]].pop(0) #remove the fixer
            result = nums_d.get(sub_target)#hash table to search 

            if result: 
                return [i, result[0]]
        return []

I strives hours for this solution but found that answer accepted but not passed Score 60.

Runtime: 60 ms, faster than 46.66% of Python3 online submissions for Two Sum. Memory Usage: 16.1 MB, less than 5.08% of Python3 online submissions for Two Sum.

I want to refactor the codes so that to achieve at least faster than 60%.

Could you please provide hints?

  • 1
    \$\begingroup\$ Take care not to misuse the term refactoring when you just mean rewriting. \$\endgroup\$ Mar 22 '19 at 12:26

First some stylistic points

  • nums_d.setdefault(nums[i], []).append(i)

    The setdefault is unnecessary here, you can assign a list normally

    nums_d[nums[i]] = [i]
  • When you need both the index and the element use enumerate see PEP279

    nums_d = {}
    for i in range(len(nums)):
        nums_d.setdefault(nums[i], []).append(i)
    nums_d = {}
    for i, e  in enumerate(nums):
        nums_d[e] = [i]
  • Use comprehension when possible (They use the C style looping and is considered to be faster)

    nums_d = { e: [i] for i, e  in enumerate(nums) }


You loop over nums twice, but this can be done in one loop! To make it O(n)

Whenever you visit a new element in nums ->

Check if it's sum complement is in nums_d, else add the target - element to the dictionary with the index as value t - e : i

nums_d = {}
for i, e in enumerate(nums):
    if e in nums_d:
        return [nums_d[e], i]
    nums_d[target - e] = i 

  • 1
    \$\begingroup\$ Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append. \$\endgroup\$
    – Graipher
    Mar 23 '19 at 11:17
  • 2
    \$\begingroup\$ @Graipher True, a defaultdict might be more appropriate there. \$\endgroup\$
    – Ludisposed
    Mar 23 '19 at 16:28
  • \$\begingroup\$ \$O(2n) = O(n).\$ \$\endgroup\$ Mar 29 '19 at 0:23

You may assume that each input would have exactly one solution.

So there's no need to iterate over num twice. In fact, you won't even iterate over it for the full range, because you can return when you found the solution.

With the input given, I'd try this:

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

def twoSum(nums, target):
    for i in nums:
        for m in nums[nums.index(i)+1:]:
            if i + m == target:
                return [nums.index(i), nums.index(m)]

print(twoSum(nums, target))        

Say i + m is your target twoSum, you iterate over nums for each i and then look in the rest of num if there's any m for which i + m = target, and return when found.

Edit: This fails if you have duplicate integers in nums that add up to target, and it'll be slower if the solution is two elements near the end of nums.

Also: thank you for mentioning Leetcode, it's new to me. Nice!

  • 2
    \$\begingroup\$ Hey, long time no see! Unfortunately the code you've supplied is worse than the one in the question, as it takes \$O(n^2)\$ time and either \$O(n)\$ or \$O(n^2)\$ memory, depending on the GC. Where in the question it runs in \$O(n)\$ time and space. Yours is however easier to understand. \$\endgroup\$
    – Peilonrayz
    Mar 22 '19 at 22:29
  • \$\begingroup\$ Hi, yes, I know, Ludisposed pointed that out as well, hence the edit. I came across the question in Triage, and thought I might as well try an answer. Hadn't thought beyond nums given, with which it yields the answer in 1+3+1=5 iterations. I'm not familiar with O(n^2), but I guess that'd be 16 here? \$\endgroup\$
    – RolfBly
    Mar 23 '19 at 18:54
  • \$\begingroup\$ Ah, he must have deleted his comments. :( Yes it goes by the worst case, so if 11 and 15 were the targets. It's different from mathematics however, as your function runs in IIRC worst case \$\frac{n^2}{2}\$ iterations. And so it's mostly just a vague guess at performance. \$\endgroup\$
    – Peilonrayz
    Mar 23 '19 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.