Watch 10 video solutions for Maximum Ice Cream Bars, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Code with Alisha has 2,741 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
It is a sweltering summer day, and a boy wants to buy some ice cream bars.
At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the ith ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.
Note: The boy can buy the ice cream bars in any order.
Return the maximum number of ice cream bars the boy can buy with coins coins.
You must solve the problem by counting sort.
Example 1:
Input: costs = [1,3,2,4,1], coins = 7 Output: 4 Explanation: The boy can buy ice cream bars at indices 0,1,2,4 for a total price of 1 + 3 + 2 + 1 = 7.
Example 2:
Input: costs = [10,6,8,7,7,8], coins = 5 Output: 0 Explanation: The boy cannot afford any of the ice cream bars.
Example 3:
Input: costs = [1,6,3,1,2,5], coins = 20 Output: 6 Explanation: The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.
Constraints:
costs.length == n1 <= n <= 1051 <= costs[i] <= 1051 <= coins <= 108Problem Overview: You are given an array costs where each value represents the price of an ice cream bar and an integer coins representing your budget. The goal is simple: buy the maximum number of bars without exceeding the available coins.
Approach 1: Greedy Algorithm using Sorting (Time: O(n log n), Space: O(1) or O(n) depending on sort)
The key observation is that cheaper bars should always be purchased first. If you spend coins on expensive bars early, you reduce the total number you can buy. Start by sorting the costs array in ascending order. Then iterate through the sorted prices and keep subtracting each cost from coins until you can no longer afford the next bar.
This works because a greedy choice—always picking the lowest cost—maximizes the count of items purchased. The algorithm performs a single pass after sorting, making it efficient and easy to implement. This approach directly uses concepts from greedy algorithms and sorting, which frequently appear together in optimization problems.
Approach 2: Counting Sort Optimization (Time: O(n + maxCost), Space: O(maxCost))
The sorting step can be avoided when the price range is reasonably bounded. Instead of sorting the entire array, build a frequency array where each index represents a price and the value represents how many bars have that price. This technique is essentially counting sort.
Once the frequency table is built, iterate from the smallest price upward. For each price p, determine how many bars you can afford: min(freq[p], coins // p). Deduct the corresponding cost from coins and update the purchased count. Because prices are processed in ascending order, you still maintain the greedy property without performing a full comparison-based sort.
This approach runs in linear time relative to the number of bars plus the maximum cost value. It is particularly useful when max(costs) is small compared to n log n, making it faster than traditional sorting.
Recommended for interviews: The sorting-based greedy solution is what most interviewers expect first. It clearly demonstrates recognition of the greedy pattern and produces a clean O(n log n) solution. Mentioning the counting sort optimization shows deeper understanding of algorithmic tradeoffs and when specialized linear-time techniques outperform comparison sorting.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) to O(n) | General case; simplest and most common interview solution |
| Counting Sort Optimization | O(n + maxCost) | O(maxCost) | When cost values are bounded and you want linear-time performance |