1833. Maximum Ice Cream Bars

Array
Greedy
Sorting
Counting Sort

TIME

O(n + m)

SPACE

O(m)

Intuition

To maximize count, buy cheapest items first. Use counting sort to efficiently process items by cost in ascending order without explicit sorting.

Solution

Build frequency array: Count how many ice creams exist at each price point.
Iterate from cheapest: Process costs from 1 to maxCost.
Buy greedily:
- If we can afford all items at current cost: buy all, subtract total cost
- If we can't afford all: buy as many as possible (coins / cost), then stop
Return count: Total number of ice creams purchased.

Why Counting Sort?

Problem explicitly requires counting sort
Efficient when cost range is bounded: O(n + maxCost)
Avoids O(n log n) comparison sort

Complexity

Time: O(n + m) where n = number of items, m = max cost
Space: O(m), frequency array

Edge Cases

Can't afford any → return 0
Can afford all → return n
Large coins value → use long in Java to prevent overflow on cost * frequency

Code

from typing import List


class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        """
        1833. Maximum Ice Cream Bars
        Time: O(n + m)
        Space: O(m)
        """
        max_cost = max(costs)
        frequency = [0] * (max_cost + 1)
        for cost in costs:
            frequency[cost] += 1

        answer = 0

        for cost in range(1, max_cost + 1):
            total_cost = cost * frequency[cost]
            if coins >= total_cost:
                coins -= total_cost
                answer += frequency[cost]
            else:
                answer += coins // cost
                break

        return answer

/**
 * 1833. Maximum Ice Cream Bars
 * Time: O(n + m)
 * Space: O(m)
 */
class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int maxCost = 0;
        for (int c : costs) {
            maxCost = Math.max(maxCost, c);
        }

        int[] freq = new int[maxCost + 1];
        for (int c : costs) {
            freq[c]++;
        }

        int count = 0;

        for (int cost = 1; cost <= maxCost; cost++) {
            if (freq[cost] == 0) continue;

            long totalCost = (long) cost * freq[cost];

            if (coins >= totalCost) {
                coins -= totalCost;
                count += freq[cost];
            } else {
                count += coins / cost;
                break;
            }
        }

        return count;
    }
}