HackerRank Hash Tables: Ice Cream Parlor solution in python

This is solution for HackerRank Hash Tables: Ice Cream Parlor challenge, in python. This is a problem in the Interview Preparation Kit > Search Algorithms and is considered of medium difficulty.

The problem

The problem is simple: 2 friends want to buy ice cream and they must spend all their money each trip. some rules:

• Every flavor has a different value.
• They must choose the flavors (numbered) to sum up to money they have
• they can't buy the same flavor
• You need to return the index starting by 1 (not 0)

The naive solution

The naive solution is to traverse the entire set almost twice. Almost because for friend 2 we will traverse only the positions not chose yet

# inefficient, naive solution: O(n²)
def whatFlavors_inneficient(cost, money):
    for i1, c1 in enumerate(cost, 1):
        for i2, c2 in enumerate(cost[i1:], i1 + 1):
            if (c1 + c2) == money:
                print(i1, i2)
                return

The final solution

In the final solution, we must trade time for space, creating a dictionary. The reason is to find, after we spend the money on the first ice cream, if there is another flavor to sum up to the money we got there.

    # cost: [1, 4, 5, 3, 2]
    dcost = dict(enumerate([c for c in cost], 1))
    # {1: 1, 2: 4, 3: 5, 4: 3, 5: 2}
    dcost = {v: k for k, v in dcost.items()}
    # {1: 1, 4: 2, 5: 3, 3: 4, 2: 5}

So, we still need to traverse all the flavors, but just once.

The complete solution is as follows

def whatFlavors(cost, money):
    # inverted (v,k) dictionary of costs
    # to find easily the value that complements the first iteration
    dcost = dict(enumerate([c for c in cost], 1))
    dcost = {v: k for k, v in dcost.items()}

    # traverse once
    for i1, c1 in enumerate(cost, 1): 
        # the cost of second ice cream must be
        c2 = money - c1
        i2 = dcost.get(c2)
        # if found, return
        if i2 and (i2 != i1):
            print(i1, i2)
            return