Maximum Ice Cream Bars

Maximum Ice Cream Bars

What is this problem about?

The Maximum Ice Cream Bars coding problem gives you an array of ice cream costs and a number of coins. You want to buy as many ice cream bars as possible. There is no constraint on which bars you can buy — just maximize the count. This is a classic greedy problem with a twist on how you implement the sort efficiently.

Why is this asked in interviews?

Amazon and other companies use this problem as a greedy sorting warm-up. While the approach is straightforward (sort and greedily buy cheapest first), the interesting angle is using counting sort to achieve O(n + max_cost) time instead of O(n log n). This tests whether candidates know when to apply non-comparison-based sorting for integer inputs with bounded range.

Algorithmic pattern used

The optimal approach uses counting sort + greedy. Count the frequency of each price. Iterate from cheapest to most expensive, buying as many of each price as possible (limited by count and remaining coins). This is O(n + max_cost) time and O(max_cost) space — optimal for the given constraints. Alternatively, standard sort + greedy is O(n log n) and also acceptable, but less impressive in interviews.

Example explanation

Costs: [1, 3, 2, 4, 1], coins = 7.

• Sorted: [1, 1, 2, 3, 4].
• Buy 1: coins = 6, count = 1.
• Buy 1: coins = 5, count = 2.
• Buy 2: coins = 3, count = 3.
• Buy 3: coins = 0, count = 4.
• Can't buy 4 (need 4, have 0).
• Answer = 4.

With counting sort: freq[1]=2, freq[2]=1, freq[3]=1, freq[4]=1. Same traversal, same result.

Common mistakes candidates make

• Sorting in descending order: Buying expensive first maximizes spending, not count. Always sort ascending for count maximization.
• Not handling coins = 0 edge case: The loop should terminate immediately when coins run out.
• Forgetting to cap purchases by available count: When using counting sort, you can't buy more than freq[price] bars at a given price.

Interview preparation tip

For the Array Sorting Counting Sort Greedy interview pattern, whenever the problem says "maximize count, minimize cost per item," immediately reach for greedy with sort. Mention the counting sort optimization to demonstrate awareness of linear-time sorting alternatives when input values are bounded integers.