HackerRank Binary Search: Ice Cream Parlor

Given an integer, the budget for two ice creams, and a list of integer, the price of the available flavors, return the 1-based indeces for the two chosen flavors. As stated in the page problem, we should implement a binary search in our solution.

I converted the provided samples in python tests, and I added to them a couple more when I was thinking on possible algorithms:

def test_provided_1(self):
    self.assertEqual('1 4', solution(4, [1, 4, 5, 3, 2]))

def test_provided_2(self):
    self.assertEqual('1 2', solution(4, [2, 2, 4, 3]))

def test_expensive(self):
    self.assertEqual('3 4', solution(10, [2, 2, 4, 6]))

def test_neighbor(self):
    self.assertEqual('3 4', solution(8, [1, 2, 4, 4, 8]))

Instead of using the suggestion given away in the title, I have been magnetically attracted to use a dictionary. The idea is quite simple, I use as key the flavor price, on which I have to perform the search, and as values a keep a list, so that I can push in it the position of all the flavor having the same price.

def solution(money, prices):
    counter = defaultdict(list)  # 1
    for i in range(len(prices)):  # 2
        counter[prices[i]].append(i+1)

    for price, flavors in counter.items():  # 3
        target = money - price
        if target == price:  # 4
            if len(flavors) > 1:
                return '{0} {1}'.format(flavors[0], flavors[1])
        else:
            others = counter.get(target)  # 5
            if others:
                result = sorted([others[0], flavors[0]])
                return '{} {}'.format(*result)

1. When I try to access a value in this dictionary, if the key was not already in, a new empty list is created. Using defaultdict saves my to call setdefault() on a plain dict.
2. I loop on the input array of prices, appending each flavor position (adjusted to be 1-based) to the associated key reporting its price.
3. Loop on all the price/flavors in the dictionary.
4. If the price I am ready to pay for the second flavor is the same of the amount I would pay for the first, I have only to check if the current bucket is used by more than one flavor. If so, I return the first two of them I found.
5. Otherwise, I check if there is in the dictionary a flavor for the price I am willing to pay. If I see it, I sort the two flavors position (as required by the problem) and return them.

This solution works fine, it is clear and fast, and it is accepted by HackerRank. However it is not what we are expected to produce. So I refactored it to use binary search. The rationale behind it could be thought as if we should run this algorithm in an embedded environment, and we found out that using hash tables eats too much memory, so we need to fall back to a slightly slower algorithm that uses a leaner data structure.

What I do now is putting price/flavors couples in a plain list, sort it and then checking for each element if there is a match to it among the other ones.

def solution(money, prices):
def solution(money, prices):
    counter = sorted([(price, flavor+1) for flavor, price in enumerate(prices)])  # 1
    for i in range(len(counter)):
        other = find_other(counter, i, money - counter[i][0])  # 2
        if other:
            result = sorted([counter[i][1], other])
            return '{} {}'.format(*result)

1. In this list comprehension I enumerate the prices. This generates a number of tuples in the format (index, price), I reverse them, increase the index, since we need it as 1-based, and push them in the list. Then I sort it.
2. For each element in the list, I check if there is a match. I pass to the find_other() function, see it below, the list, the current position, the amount I want spend for the ice cream. I expect it to return the other flavor or nothing, in the sense of python None, if it couldn't find it.

Here I finally perform the binary search:

def find_other(counter, pos, price):
    left = pos+1  # 1
    right = len(counter)-1
    while left <= right:  # 2
        mid = (left + right) // 2
        if counter[mid][0] == price:
            return counter[mid][1]

        if counter[mid][0] > price:
            right = mid-1
        else:
            left = mid+1
    return None

1. I don't care about the left-side elements in the counter list, they have been already checked. This saves some minimal searching time and, more interestingly, avoid the risk of a false positive. Think the case that the total budget is 2x and I am looking for a flavor costing x. I could end up finding the same x I have already found. It won't be difficult to skim this case off, but in this way we have it for free.
2. If there is anything in the current interval, I get its central point, I check it against the expected value, if it is not a match move to the side where I could find it.

Also this solution works fine and it is accepted by HackerRank.

On GitHub: The unit test, the binary search version, and the unofficial hash map version.