9
\$\begingroup\$

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.

Example:

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)

Implement

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?

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

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) }
    

Hint

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 

\$\endgroup\$
  • 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 at 11:17
  • 2
    \$\begingroup\$ @Graipher True, a defaultdict might be more appropriate there. \$\endgroup\$ – Ludisposed Mar 23 at 16:28
  • \$\begingroup\$ \$O(2n) = O(n).\$ \$\endgroup\$ – Solomon Ucko Mar 29 at 0:23
0
\$\begingroup\$

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!

\$\endgroup\$
  • 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 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 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 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.