LeetCode 1833 - Maximum Ice Cream Bars

LeetCode Problem 1833

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Counting Sort

Solution

Problem Understanding

This problem asks us to determine the maximum number of ice cream bars a boy can buy with a limited number of coins. The input consists of an array costs, where costs[i] represents the price of the i-th ice cream bar, and an integer coins representing the total coins available. The boy can purchase the bars in any order, but cannot exceed his coin budget. The expected output is a single integer representing the maximum number of bars he can buy.

Constraints tell us that the number of bars, n, can be as large as 100,000 and the individual costs as high as 100,000. The coin budget can reach 100 million. This scale makes naive approaches like trying all subsets or sorting with a standard comparison-based sort suboptimal for very large inputs.

Important edge cases include arrays where all costs exceed coins (resulting in zero bars bought), arrays where coins is sufficient to buy all bars, and arrays where many bars have the same cost. The problem guarantees that costs and coins are positive integers.

Approaches

The brute-force approach involves iterating through all subsets of costs to find the largest subset whose sum does not exceed coins. While this gives the correct answer, the number of subsets grows exponentially (O(2^n)), which is infeasible for n up to 100,000.

A better approach is a greedy strategy: buy the cheapest bars first. Sorting the array and iteratively subtracting the bar cost from coins until we cannot afford more bars achieves this. Standard sorting would take O(n log n), but the problem specifically asks for a counting sort solution. Counting sort works because the costs are integers within a bounded range (1 to 100,000). We count the occurrences of each cost and then iterate from the cheapest to the most expensive, purchasing as many bars as possible without exceeding the coin budget.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generate all subsets and check sums, impractical for large n
Optimal (Counting Sort + Greedy)	O(n + m)	O(m)	Count occurrences of each cost, iterate from cheapest to most expensive; m is max cost

Algorithm Walkthrough

1. Initialize a counting array of size max_cost + 1, where max_cost is the maximum possible cost (100,000). Each index i in this array represents how many bars cost exactly i coins.
2. Populate the counting array by iterating over costs. For each cost, increment the corresponding index in the counting array. This efficiently groups bars by cost without sorting.
3. Initialize counters for bars_bought = 0 and start iterating from the smallest cost to the largest.
4. For each cost i:

• Calculate how many bars of this cost can be bought with the remaining coins: buy = min(count[i], coins // i).
• Increment bars_bought by buy.
• Subtract buy * i from coins.
• If coins becomes zero, break early as no more bars can be purchased.

5. Return bars_bought as the maximum number of ice cream bars the boy can buy.

Why it works: The counting sort ensures we process bars in ascending order of cost. By always buying the cheapest available bars first, we maximize the number of bars purchased. The algorithm terminates when either we run out of coins or we have considered all bar prices.

Python Solution

from typing import List

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        max_cost = max(costs)
        count = [0] * (max_cost + 1)
        
        # Populate counting array
        for cost in costs:
            count[cost] += 1
        
        bars_bought = 0
        for price in range(1, max_cost + 1):
            if count[price] == 0:
                continue
            buy = min(count[price], coins // price)
            bars_bought += buy
            coins -= buy * price
            if coins == 0:
                break
                
        return bars_bought

The Python implementation first finds the maximum cost to allocate the counting array efficiently. Then it counts occurrences of each cost and iterates over the costs in ascending order. For each cost, it calculates the number of bars affordable with remaining coins, updates the total bars bought, and reduces the coin count. The loop breaks early if coins run out, improving efficiency.

Go Solution

func maxIceCream(costs []int, coins int) int {
    maxCost := 0
    for _, c := range costs {
        if c > maxCost {
            maxCost = c
        }
    }

    count := make([]int, maxCost+1)
    for _, c := range costs {
        count[c]++
    }

    barsBought := 0
    for price := 1; price <= maxCost; price++ {
        if count[price] == 0 {
            continue
        }
        buy := count[price]
        if coins/price < buy {
            buy = coins / price
        }
        barsBought += buy
        coins -= buy * price
        if coins == 0 {
            break
        }
    }

    return barsBought
}

In Go, we explicitly calculate the maximum cost to size the counting array. The rest of the logic mirrors Python. Integer division automatically handles how many bars we can buy. Go’s slices handle memory allocation, and integer operations are safe given constraints.

Worked Examples

Example 1: costs = [1,3,2,4,1], coins = 7

Iteration	Cost	Count	Buy	Bars Bought	Coins Remaining
1	1	2	2	2	5
2	2	1	1	3	3
3	3	1	1	4	0

Output: 4

Example 2: costs = [10,6,8,7,7,8], coins = 5

Iteration	Cost	Count	Buy	Bars Bought	Coins Remaining
1	6	1	0	0	5
...	>6	...	0	0	5

Output: 0

Example 3: costs = [1,6,3,1,2,5], coins = 20

Iteration	Cost	Count	Buy	Bars Bought	Coins Remaining
1	1	2	2	2	18
2	2	1	1	3	16
3	3	1	1	4	13
4	5	1	1	5	8
5	6	1	1	6	2

Output: 6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Counting array construction is O(n), iterating through costs is O(m) where m is max cost
Space	O(m)	Counting array of size max_cost + 1

The time complexity is efficient because we avoid full sorting and leverage bounded integer costs. Space complexity is reasonable since max_cost is at most 100,000.

Test Cases

# Provided examples
assert Solution().maxIceCream([1,3,2,4,1], 7) == 4  # standard example
assert Solution().maxIceCream([10,6,8,7,7,8], 5) == 0  # cannot buy any
assert Solution().maxIceCream([1,6,3,1,2,5], 20) == 6  # can buy all

# Edge cases
assert Solution().maxIceCream([], 10) == 0  # no ice cream bars
assert Solution().maxIceCream([1,1,1,1], 0) == 0  # no coins
assert Solution().maxIceCream([5,5,5,5], 20) == 4  # exact coins for all
assert Solution().maxIceCream([5,5,5,5], 19) == 3  # not enough for all
assert Solution().maxIceCream([100000]*100000, 100000000) == 1000  # stress test max cost and n

Test	Why
Empty array	Validates no bars edge case
No coins	Validates insufficient budget
Exact coins