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

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

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:
            results.add(tuple(sorted((indict[key], indict[diff]))))
        
        
    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