< Back




1833. Maximum Ice Cream Bars

Kid's got some coin to buy some ice cream bars. How many ice cream bars can we purchase before he
runs out of money?

Regular greedy problem, and we can using counting sort to get the optimal time. We go ahead and count
the frequency of ice cream bars with the same value. We also find the minimum and maximum cost from
the ice cream bars available.

Iterating from the min to the max, we check how much money we can spend on this bucket of ice cream
bars. This will be the minimum between the number of ice cream bars available, and if we can afford
any ice cream bars in this bucket. If we can afford ice cream bars in this bucket, we'll buy as many
as possible. If we can't afford ice cream bars in this bucket, we terminate because we've can't
afford more expensive buckets, either.

We keep track of how many coins we've spent so far, and we update how many ice cream bars we've
purchased during each iteration through the buckets.

The solution is as follows:


  from collections import Counter

  class Solution:
      def maxIceCream(self, costs: List[int], coins: int) -> int:
          min_cost, max_cost = min(costs), max(costs)
          counts = Counter(costs)
          ans = spent = 0

          for i in range(min_cost, max_cost + 1):
              if counts.get(i, 0):
                  spend = min(counts[i], (coins - spent) // i)

                  if not spend:
                      break

                  ans += spend
                  spent += spend * i

          return ans


_ Time Complexity:

  O(n + m) - We find the min and max of the costs for ice cream bars. We also iterate over our
  frequency counts.

_ Space Complexity:

  O(m) - We store m frequencies of ice cream bar costs.