LeetCode 1833: Maximum Ice Cream Bars – Java Greedy Solution Explained
Buy the Maximum Number of Ice Cream Bars Using Sorting and Greedy Strategy
Introduction
LeetCode 1833, Maximum Ice Cream Bars, is a classic Greedy Algorithm problem that teaches an important optimization principle:
When you want to maximize the number of items purchased with a limited budget, always buy the cheapest items first.
Although the problem statement specifically mentions solving it using Counting Sort, understanding the Greedy approach first helps build intuition before moving to the optimized counting-sort solution.
In this article, we'll cover:
- Problem intuition
- Greedy strategy
- Sorting-based solution
- Counting Sort optimization
- Dry run examples
- Complexity analysis
- Interview insights
Problem Statement
Problem Link -: Maximum Ice Cream Bars
A boy has a fixed number of coins.
You are given:
which represents the price of the ith ice cream bar.
The boy can purchase ice cream bars in any order.
Your task is to determine the maximum number of ice cream bars that can be bought without exceeding the available coins.
Example 1
Input
Output
Explanation
Sort the costs:
Buy in order:
Total bars purchased:
Example 2
Input
Output
Even the cheapest ice cream costs more than the available coins.
Example 3
Input
Output
The boy can purchase every ice cream bar.
Key Observation
Suppose you have:
and:
Buying:
allows only:
Total bars:
But buying cheapest first:
Not possible.
Try:
Still leaves room for more purchases in many cases.
To maximize quantity:
Always buy the cheapest available ice cream first.
This immediately suggests a Greedy strategy.
Approach 1: Sorting + Greedy
Steps
- Sort the array.
- Buy ice creams from cheapest to most expensive.
- Stop when coins run out.
- Return the count.
Java Solution
Dry Run
Input
After Sorting
Purchase Process
Buy first:
Buy second:
Buy third:
Buy fourth:
Cannot buy:
Final answer:
Why Greedy Works
The goal is:
not:
Choosing a more expensive ice cream earlier can only reduce the number of future purchases.
Therefore:
Picking the cheapest available option is always optimal.
This makes Greedy the correct strategy.
Follow-Up: Counting Sort Solution
The problem explicitly asks:
You must solve it using Counting Sort.
Why?
Because:
The cost values have a bounded range.
Instead of sorting:
we can count frequencies.
Counting Sort Approach
Step 1
Create frequency array.
Step 2
Count occurrences.
Step 3
Process costs from smallest to largest.
Optimized Counting Sort Solution
Complexity Analysis
Sorting Solution
Time Complexity
Space Complexity
(ignoring sorting implementation details)
Counting Sort Solution
Time Complexity
Effectively linear.
Space Complexity
for the frequency array.
Which Solution Should You Use?
| Approach | Time | Space |
| Sorting + Greedy | O(n log n) | O(1) |
| Counting Sort | O(n + 100000) | O(100000) |
For interviews:
- Explain the Greedy idea first.
- Mention Sorting solution.
- Then discuss Counting Sort because the problem explicitly requires it.
This demonstrates both problem-solving ability and optimization awareness.
Common Mistakes
Mistake 1
Buying expensive bars first.
Mistake 2
Stopping after a single unaffordable item in an unsorted array.
Always sort or process costs in increasing order.
Mistake 3
Ignoring the Counting Sort requirement.
The online judge may accept sorting, but interviewers may specifically ask for the linear-time optimization.
Key Takeaways
- The problem is based on Greedy selection.
- To maximize purchases, buy the cheapest items first.
- Sorting provides a simple solution.
- Counting Sort satisfies the problem's follow-up requirement.
- Greedy works because every expensive purchase reduces future buying power.
- Counting Sort improves performance when value ranges are bounded.
Conclusion
LeetCode 1833: Maximum Ice Cream Bars is an excellent Greedy Algorithm problem that demonstrates how local optimal choices can lead to a globally optimal solution.
The sorting-based approach is intuitive and easy to implement, while the counting-sort optimization leverages the bounded range of costs to achieve near-linear performance.
Understanding both approaches prepares you not only for coding interviews but also for real-world optimization problems involving budgets, resources, and constrained selections.
