11 Dec 2023

Posted on:

10 Dec 2023

0

# Resolved:Two Sum problem - Solution with pre-generated dictionary

Are there any downsides to my solution of this problem?

``````def two_sum_dict(inlist, target):
indict = {v:i for i,v in enumerate(inlist)}
for key in indict:
diff = target - key
if diff in indict:
return indict[key], indict[diff]
return -1``````

Instructor
Posted on:

11 Dec 2023

0

Hey Klim,

Thank you for reaching out and well done! The solution that you share is a great alternative to the code suggested in the lesson. With a bit of fine-tuning to account for all potential solutions, it could be even more effective.

In the video lesson, we defined the following list:

``L2 = [2, 5, 3, 7, 4]``

When searching for all pairs that add up to 10, there are two possible answers: `(2, 3)` and `(1, 1)`. That is because both 3+7 and 5+5 add up to 10. Giles' solution identifies only the first pair, while your solution finds only the second. Hence, both solutions are somewhat incomplete. I encourage you to consider ways to refine your code so it can identify all possible answers. If you need a bit of guidance, I'll share one approach to solving this problem below.

The reason your code outputs the result `(1, 1)` lies in the arrangement of numbers in the list. When the code encounters the number 5, it calculates the difference between 10 and 5, and then looks for this difference in the `indict` dictionary. Finding the number 5 in the dictionary, the code returns the result without exploring further. However, if the items in the list were arranged as follows:

``L2 = [2, 7, 3, 5, 4]``

your code would return (1, 2), thereby missing another valid solution, which is (3, 3).

To address this, let's proceed in a step-by-step manner. First, rather than immediately returning the result within the `for`-loop, we could create a list named `results` to accumulate all valid solutions. We'll then return the `results` variable outside the loop.

``````def two_sum_dict(inlist, target):
indict = {v:i for i,v in enumerate(inlist)}

results = []

for key in indict:
diff = target - key
if diff in indict:
results.append((indict[key], indict[diff]))

return results``````
Instructor
Posted on:

11 Dec 2023

0

Upon applying this code to `L2 = [2, 5, 3, 7, 4]`, we obtain the result `[(1, 1), (2, 3), (3, 2)]`. While this successfully captures all viable solutions, it also includes duplicates, specifically `(2, 3)` and `(3, 2)`.

To eliminate these duplicates, we can convert the `results` variable into a set, as sets inherently remove duplicate elements.  However, since Python treats `(2, 3)` and `(3, 2)` as distinct due to their order, we need to sort each pair before adding it to the set. This can be done using Python's `sort()` function. As `sort()` outputs a list, we must then convert this sorted list back into a tuple using the `tuple()` function. Consequently, the final version of the code would be as follows:

``````def two_sum_dict(inlist, target):

indict = {v:i for i,v in enumerate(inlist)}

results = set()

for key in indict:
diff = target - key
if diff in indict:

return results``````

This enhanced version of the code retrieves all possible solutions without duplicating them.

Hope you find this answer helpful! If you've come up with an alternative solution to this problem, I'd be happy to hear about it.

Kind regards,
365 Hristina