Maximum Ice Cream Bars

You are given an array costs where costs[i] is the price of the i-th ice cream bar, and an integer coins representing your total budget. You want to buy as many ice cream bars as possible. Return the maximum number of ice cream bars you can buy.

This is LeetCode 1833: Maximum Ice Cream Bars, a medium problem that demonstrates how sorting enables a clean greedy strategy. The core idea is simple: if you want to maximize the number of items you can buy with a limited budget, always buy the cheapest item available first.

Why this problem matters

The "sort then greedily select" pattern is one of the most common greedy techniques in algorithm design. You will see it in problems about scheduling, resource allocation, and task selection. Maximum Ice Cream Bars is a clean introduction because the greedy argument is intuitive: spending less on each item leaves more budget for future items, so buying cheap items first can never be worse than buying expensive ones first.

Once you internalize this pattern, you can apply it to dozens of other problems without reinventing the logic each time.

The key insight

Sort the costs in ascending order, then iterate through the sorted array. For each ice cream bar, if you can afford it, buy it and subtract the cost from your remaining coins. The moment you encounter a bar you cannot afford, stop. Because the array is sorted, every remaining bar is at least as expensive, so you cannot afford any of them either.

This greedy choice is provably optimal. Suppose there were a better solution that skipped a cheaper bar and bought a more expensive one instead. You could swap the expensive bar for the cheaper one, spend less, and still have at least as many bars. So no solution that skips a cheaper bar can beat the greedy approach.

The solution

def max_ice_cream(costs: list[int], coins: int) -> int:
    costs.sort()
    count = 0
    for cost in costs:
        if coins >= cost:
            coins -= cost
            count += 1
        else:
            break
    return count

Here is what each piece does:

1. costs.sort() arranges the prices from smallest to largest. This is the key step that makes the greedy strategy work.
2. We iterate through the sorted costs. For each bar, we check whether we have enough coins to buy it.
3. If we can afford it, we subtract the cost from coins and increment count.
4. If we cannot afford it, we break out of the loop. Since the array is sorted, all remaining bars cost at least as much as this one, so there is no point continuing.
5. We return count, the total number of bars purchased.

Visual walkthrough

After sorting costs to [1, 1, 2, 3, 4] with coins = 7, we buy the first four bars for a total of 1 + 1 + 2 + 3 = 7. We have 0 coins left and cannot afford the last bar (cost 4). The answer is 4.

Complexity analysis

Sorting the array takes O(n log n). The greedy pass through the sorted array is O(n). Combined, the dominant term is O(n log n). Space is O(1) if you sort in place (which Python's list.sort() does). If you use sorted() instead, that creates a copy and uses O(n) space.

This is optimal for a comparison-based approach. You need to examine every element at least once, and the sort is the bottleneck. If the costs were bounded by a small constant, you could use counting sort for O(n) time, but that is rarely expected in interviews.

The building blocks

1. Sort-then-greedy pattern

The pattern of sorting input to enable a simple greedy pass:

items.sort()
result = 0
for item in items:
    if can_include(item):
        include(item)
        result += 1
    else:
        break

In Maximum Ice Cream Bars, we sort costs and greedily buy the cheapest. In Assign Cookies, we sort both children and cookies and greedily match. In Minimum Number of Arrows to Burst Balloons, we sort intervals and greedily merge overlapping groups. The skeleton is the same: sort first, then process items in order, making the locally optimal choice at each step.

2. Budget/capacity greedy selection

The pattern of selecting items under a budget constraint to maximize count:

budget = total_budget
count = 0
for cost in sorted_costs:
    if budget >= cost:
        budget -= cost
        count += 1
    else:
        break
return count

This template applies any time you want to maximize the number of items you can afford. The key property is that all items contribute equally (each counts as 1), so cheaper items are always preferable. If items had different values, you would need a knapsack approach instead.

Edge cases

• All bars cost the same costs = [3, 3, 3], coins = 9: you buy all three. No sorting effect, but the algorithm handles it naturally.
• Cannot afford any bar costs = [5, 10], coins = 2: the cheapest bar costs 5, which exceeds 2. Return 0.
• Can afford all bars costs = [1, 1, 1], coins = 100: buy everything. Return len(costs).
• Single bar costs = [4], coins = 4: exactly enough for one bar. Return 1.
• Single bar, not enough costs = [4], coins = 3: cannot afford it. Return 0.
• Large input costs with 10^5 elements: sorting is O(n log n), which is well within time limits.
• Coins equals zero costs = [1, 2], coins = 0: cannot buy anything. Return 0.

From understanding to recall

You have read the sort-then-greedy solution and it makes sense. Sort, iterate, buy while you can, stop when you cannot. But can you write it from scratch in an interview without looking back?

The details matter: remembering to sort first, using >= instead of > when comparing coins to cost, breaking early instead of continuing, and returning the count rather than the remaining coins. These are small but easy to fumble under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the sort-then-greedy loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize count under a budget" and the code flows out without hesitation.

The sort-then-greedy pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Assign Cookies - Another greedy problem where sorting enables optimal assignment
• Lemonade Change - Greedy change-making with limited resources
• Minimum Number of Arrows to Burst Balloons - Sort-then-greedy on intervals

CodeBricks breaks the maximum ice cream bars LeetCode problem into its sort-then-greedy and budget selection building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy budget question shows up in your interview, you do not think about it. You just write it.