We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

The beauty of such questions is that there is no one answer, but seeing as this is a training/learning manual, we should expect to be presented with the best solutions all the time.

This question has been forced into a binary search context for the sake of it.

I totally agree with you. I have rated this question with what it deserve. At least we should do that, so that such questions do not make up to the board.

Thanks for the supplement. I solved it this way though I have a doubt. This code will not return correct value for following data set

11672785838

Correct result should be 3,5 while this will return 3,7. Although none of the TC has this sort of data, this should be tackled in the code. What do you say?

My hash impl returned 3,5. Hash impl is O(n) space and time. BS impl is O(nlogn) time, O(n) space. Justifying a sub-optimal answer as a "learning experience" without providing a progression of improvements seems poor form, and would not suffice in an interview or in the real world imo.

Eg : 2 2 3 4
here, while inserting in map, as 2 has already been insertes, so while at index 1 , u checked whether 2 + 2 == money, otherwise did,t considered it ??

I agree with you but for learning purposes it's good to solve it using binary search because you might get faced with one problem later that requires you to modify the original algorigthm because it might be dificult/impossible to solve it using native methods.

Even cheaper than a hash map (but still basically a hashmap) would be to use a simple integer array. Costs are limited to 10000. So create an array[10000], indexed by cost, which stores the flavor id. With Java, this is pre-initialized to zero. For each flavor, see if the matching flavor is in the array: arr[m-newCost] != 0.

If it's there, the match is found. If not, store this item in the array.

Even though there is only 1 unique solution, you have to continue reading until the input for the "trip" is completed.

The editorial says it is a O(n) solution, using binary search. But the array had to be sorted first, so it started with a O(nlogN) solution. By iterating over the array, and making binary search calls, it would be O(nlogN) by itself.

Using a map, we could get a O(n) solution. But, by using binary search, the space complexity does not increase, at least. It wouldn´t make a difference if the array was already sorted, in this case, because the complexity would not change by sorting it or not.

HOLD ON. I just reviewed the YouTube video from Gayle McDowell on this; and the reason why this is actually a Binary Search problem rather than a HashMap problem is this: For the case where you have two different ice cream flavors with the same cost. You need to be able to distinguish between them; and a HashMap from Cost to Flavor overwrites with the latest Flavor value for the same Cost Key. I worked through the coding solution to this with hints from that video here: https://www.youtube.com/watch?v=Ifwf3DBN1sc

That's not a problem. For each value, check if the compliment is in the keys of the map. If it is then you've found your pair, duplicate or not. If it isn't then add the cost of the flavour to the map. O(n) and you don't need any special consideration for the case when the answer is two ice creams with the ame cost. Example in Python3:

I just ran a small test to check if the Map[cost] to FlavorIdx approach has a bug in it. It does. This is why Gayle's YouTube video uses BinarySearch on Cost entries ordered by FlavorIdx.

In this test sequence; the Flavor at position 2 overwrites/loses the flavor at position 1.

What's interesting though; is that this test case appears to be missing from the Hacker Rank test suite; because this Map[cost] code approach was passing all of their test suite.

Here's my Python code (formatted on next comment):

deffind_matched_flavors(m,a):print"TOTAL MONEY is: {0}".format(m)cost_map={}fori,costinenumerate(a):print"(i, cost) is ({0},{1})".format(i,cost)sunny=costjohnny=m-costprint"prior cost_map {0}".format(cost_map)print"johnny, sunny {0}, {1}".format(johnny,sunny)ifjohnnyincost_map.keys():print"FOUND MATCHED FLAVORS IN ORDER OFFSET +1:"printcost_map[johnny]+1,i+1# BUGFIXED: following else blocks add of NEW cost:flavorIdx if complement already found pre-loaded# else:# BUG-UNFIXED: following with OVERWRITE-LOSE prior flavor with cost duplicating CURRENT flavor cost!# eg. (5, 0) gets overwritten with (5, 1)# i.e. complement must be found on FIRST cost map entry; otherwise we lose all history of# that entry when a duplicate cost entry is added!cost_map[cost]=iprint"updated cost_map {0}".format(cost_map)# MY TEST SCRIPT m=8flavorsToCost=[5,5,3,4,4]find_matched_flavors(m,flavorsToCost)

The problem specifies that there will only be one unique solution. Your test case has three valid solutions (i.e. (0,2), (1,2) and (3,4)) and so it is not a valid test case for the problem defined.

To solve this, I used a dict (Python version of hashtable) that had the cost as the key and the value was a space separated string of all the indices where that cost occured in the list.. Then it was simply a matter of splitting that string and printing the first two elements if cost_i==money-cost_i

My approach is very similar to yours, I also used python dict. But didn't you have timeout? My code passed only three test cases on time, rest of them went timeout

That behaviour is not a problem. The only situation where duplicates matter is when the cost is exactly half the money. E.g. you have 16 coins and the flavour costs 8. If there is another one costing 8, that's your solution. Other duplicates don't matter (you will never need more than one flavour with that cost). They can't even be part of the solution. Because the solution is unique as per problem description and duplicates would create multiple solutions.

For the binary search, aren't we supposed to sort the array of costs first? that's gonna be O(nlog(n)). then we will have to search the target for each one of the elements (worst case) of the array which will make it O(nlog(n)). I guess hash tables with the overall complexity of O(n) would be better than O(nlog(n)). I'm writing this to learn if there is a better solution than hash tables so I would appreciate your feedback.

The hashmap is really a good solution here, but want to mention that even in case of hashmap the complexity will be O(nlogn). This is because most of hashmaps are implemented using the self-balanced BST (mostly RB-tree) and the complexity for adding item to hashmap is O(logn).

## Hash Tables: Ice Cream Parlor

You are viewing a single comment's thread. Return to all comments →

binary search is a dumn-ass solution for this problem. This is just a two sum issue, use hashmap this could be done in O(n)

The beauty of such questions is that there is no one answer, but seeing as this is a training/learning manual, we should expect to be presented with the best solutions all the time.

This question has been forced into a binary search context for the sake of it.

I totally agree with you. I have rated this question with what it deserve. At least we should do that, so that such questions do not make up to the board.

If at least the costs were given in order, it could make sense...

agreed. my binary search attempts were timing out.

it was only when i ignored it mentioning binary search and just thought about best way to solve the problem, could I solve it without timeouts

I had the same problem. The problem as such is good but it's poorly categorized.

If the costs were given in order, a linear search for the sum starting from both ends does the job instead of doing a binary search in every step.

At least in C++, you can sort the data and then perform linear search (converging from both ends) without timing out.

[two-sum](https://leetcode.com/articles/two-sum/)

Thanks for the supplement. I solved it this way though I have a doubt. This code will not return correct value for following data set

Correct result should be 3,5 while this will return 3,7. Although none of the TC has this sort of data, this should be tackled in the code. What do you say?

HashMap in java does not let you enter duplicate keys. So in your map, the key 8 is associated with index 6

If there is only one 8 in the coins and the money is 16, will the hashMap implementation give the right answer? Since the flavours need to be distinct

My hash impl returned 3,5. Hash impl is O(n) space and time. BS impl is O(nlogn) time, O(n) space. Justifying a sub-optimal answer as a "learning experience" without providing a progression of improvements seems poor form, and would not suffice in an interview or in the real world imo.

Did you handled the duplicacy case, as:

Eg : 2 2 3 4 here, while inserting in map, as 2 has already been insertes, so while at index 1 , u checked whether 2 + 2 == money, otherwise did,t considered it ??

it is mentioned that there will be only unique solution as part of the constraints, so your test case is not correct it should not have 2 solutions

Thanks for pointing that out. I just can't find my solution to fix the test case...

There is a unique solution...it is mentioned in the problem

https://web.stanford.edu/class/cs9/sample_probs/TwoSum.pdf

This is a very useful resource. Thanks!

I agree with you but for learning purposes it's good to solve it using binary search because you might get faced with one problem later that requires you to modify the original algorigthm because it might be dificult/impossible to solve it using native methods.

Yeah no idea why this is considered a binary search problem, when even the editorial doesn't use it.

My binary search solution timed out...

Even cheaper than a hash map (but still basically a hashmap) would be to use a simple integer array. Costs are limited to 10000. So create an array[10000], indexed by cost, which stores the flavor id. With Java, this is pre-initialized to zero. For each flavor, see if the matching flavor is in the array: arr[m-newCost] != 0.

If it's there, the match is found. If not, store this item in the array.

Even though there is only 1 unique solution, you have to continue reading until the input for the "trip" is completed.

Integer array indexed by cost? What if there are two flavors with the same cost. How would you resolve that using an array?

the value of array[cost] would represent how many duplicates are in your set.

The editorial says it is a O(n) solution, using binary search. But the array had to be sorted first, so it started with a O(nlogN) solution. By iterating over the array, and making binary search calls, it would be O(nlogN) by itself.

Using a map, we could get a O(n) solution. But, by using binary search, the space complexity does not increase, at least. It wouldn´t make a difference if the array was already sorted, in this case, because the complexity would not change by sorting it or not.

Since the orger is lost after sorting..how can binary search retrun the actual index.

You can add it to an object with cost/index (struct or class)

Create an array of original indexes and sort them instead of the original values.

then u get to add n space?

agreed. ;0)

HOLD ON. I just reviewed the YouTube video from Gayle McDowell on this; and the reason why this is actually a Binary Search problem rather than a HashMap problem is this: For the case where you have two different ice cream flavors with the same cost. You need to be able to distinguish between them; and a HashMap from Cost to Flavor overwrites with the latest Flavor value for the same Cost Key. I worked through the coding solution to this with hints from that video here: https://www.youtube.com/watch?v=Ifwf3DBN1sc

But it would be easy to overcome this problem. Just make a hashtable of list of itens with this same value. Still linear time and simpler code.

That's not a problem. For each value, check if the compliment is in the keys of the map. If it is then you've found your pair, duplicate or not. If it isn't then add the cost of the flavour to the map. O(n) and you don't need any special consideration for the case when the answer is two ice creams with the ame cost. Example in Python3:

or even

@Dan_Golding

I just ran a small test to check if the Map[cost] to FlavorIdx approach has a bug in it. It does. This is why Gayle's YouTube video uses BinarySearch on Cost entries ordered by FlavorIdx.

In this test sequence; the Flavor at position 2 overwrites/loses the flavor at position 1.

What's interesting though; is that this test case appears to be missing from the Hacker Rank test suite; because this Map[cost] code approach was passing all of their test suite.

Here's my Python code (formatted on next comment):

The problem specifies that there will only be one unique solution. Your test case has three valid solutions (i.e. (0,2), (1,2) and (3,4)) and so it is not a valid test case for the problem defined.

i agree, undefined in case there are 3 (or more) similar costs.

The first one should have used a list instead of dictionary:

To solve this, I used a dict (Python version of hashtable) that had the cost as the key and the value was a space separated string of all the indices where that cost occured in the list.. Then it was simply a matter of splitting that string and printing the first two elements if cost_i==money-cost_i

My approach is very similar to yours, I also used python dict. But didn't you have timeout? My code passed only three test cases on time, rest of them went timeout

Why do you need to distinguish between them?

Thank you so much !! I had the same issue !

That behaviour is not a problem. The only situation where duplicates matter is when the cost is exactly half the money. E.g. you have 16 coins and the flavour costs 8. If there is another one costing 8, that's your solution. Other duplicates don't matter (you will never need more than one flavour with that cost). They can't even be part of the solution. Because the solution is unique as per problem description and duplicates would create multiple solutions.

Interesting I didn't get the binarySearch working in time with C++14. Using an unordered_map solved the problem however.

For the binary search, aren't we supposed to sort the array of costs first? that's gonna be O(nlog(n)). then we will have to search the target for each one of the elements (worst case) of the array which will make it O(nlog(n)). I guess hash tables with the overall complexity of O(n) would be better than O(nlog(n)). I'm writing this to learn if there is a better solution than hash tables so I would appreciate your feedback.

Better hashed than bashed.

this is not a sorted arrary binary search is not posible

Yea, ended up doing this with a hash as well, not sure what binary search was suggested here for.

The hashmap is really a good solution here, but want to mention that even in case of hashmap the complexity will be O(nlogn). This is because most of hashmaps are implemented using the self-balanced BST (mostly RB-tree) and the complexity for adding item to hashmap is O(logn).