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.
This approach involves sorting the array of costs to ensure the boy buys the cheapest available ice cream bars first. After sorting, iterate through the list and keep buying bars until you run out of coins.
Steps involve:
This C program sorts the costs array using qsort and calculates the maximum number of ice creams that can be bought while iterating through the sorted array. It returns the count of ice creams the boy can afford.
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1), as no additional space is required beyond the input.
This solution uses a variation of counting sort suitable for this specific problem due to the constraint that costs[i] <= 100,000.
Steps involve:
This Python solution uses a frequency array to store the number of each cost. By iterating over these costs in order (with known max cost), it calculates how many bars of each cost can be purchased and subtracts the respective cost from the available coins, tallying the total ice creams bought.
Python
Time Complexity: O(n + max(costs)), where max(costs) could be up to 100,000.
Space Complexity: O(max(costs)), because of the frequency array used.
To buy as many ice creams as possible, and they can be purchased in any order, we should prioritize choosing ice creams with lower prices.
Sort the costs array, and then start buying from the ice cream with the lowest price, one by one, until it is no longer possible to buy, and return the number of ice creams that can be bought.
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the costs array.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Algorithm using Sorting | Time Complexity: O(n log n) due to the sorting step. |
| Approach 2: Counting Sort Optimization | Time Complexity: O(n + max(costs)), where max(costs) could be up to 100,000. |
| Greedy + 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 |
Leetcode# 1833. Maximum Ice Cream Bars || Code + Explanation + Example Walkthrough • Code with Alisha • 2,741 views views
Watch 9 more video solutions →Practice Maximum Ice Cream Bars with our built-in code editor and test cases.
Practice on FleetCode