Hash Tables: Ice Cream Parlor

  • + 1 comment

    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.