Problem Statement in English

You’re given an array of integers costs where costs[i] is the price of the i-th ice cream bar in a store. You are also given an integer coins, the amount of coins you have.

You want to buy as many ice cream bars as possible with the given coins. You can buy the ice cream bars in any order.

Return the maximum number of ice cream bars you can buy with coins.

You must use counting sort to solve this problem.

Approach

Since we must use counting sort, we can create a frequency array to count the occurrences of each cost. Then, we can iterate through the frequency array and buy as many ice cream bars as possible for each cost until we run out of coins.

We start from the lowest cost and keep track of the total number of ice cream bars we can buy. For each cost, we calculate how many bars we can afford and update the total count and remaining coins accordingly.

And we’re done!

Solution in Python


class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        l = [0] * (max(costs) + 1)

        for c in costs:
            l[c] += 1

        res = 0

        for i in range(1, len(l)):
            bars = min(l[i], coins // i)

            res += bars
            coins -= bars * i

        return res

Complexity

  • Time: $O(n + m)$
    where $n$ is the length of the costs array and $m$ is the maximum cost in the array.

  • Space: $O(m)$
    for the frequency array.

And we are done.