Maximum Ice Cream Bars — Solution in Python, Java & C++
Maximum Ice Cream Bars solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Ice Cream Bars is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Counting Sort
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A shop sells ice cream bars; costs[i] is the price of the i-th bar. A boy has coins coins and wants as many bars as possible, not the most expensive ones.
Return the maximum number of bars he can buy.
Example 1
Input: costs = [1,3,2,4,1], coins = 7
Output: 4
Explanation: Buy the bars costing 1, 1, 2 and 3.
Example 2
Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
Example 3
Input: costs = [1,6,3,1,2,5], coins = 20
Output: 6
Constraints
1 <= costs.length <= 401 <= costs[i] <= 10001 <= coins <= 100000
Hints for Maximum Ice Cream Bars
Hint 1
Since every bar counts the same toward the answer, always buy the cheapest remaining one.
Hint 2
Sort ascending and spend until the next bar is unaffordable.
Hint 3
Because the prices are bounded, a counting sort makes it linear.
How to solve Maximum Ice Cream Bars
Every bar counts the same, so buy the cheapest bars first until the next one is unaffordable.
Approach
- Sort prices ascending.
- Spend while
price <= coins, counting bars.
Why it works
Swapping any bought bar for a cheaper unbought one never reduces the count, so the cheapest-first prefix is optimal.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- Prices are bounded, so a counting sort makes it linear.
Reference solution
Python
def maxIceCream(costs, coins: int) -> int:
bought = 0
for price in sorted(costs):
if price > coins:
break
coins -= price
bought += 1
return boughtJava
public static int maxIceCream(int[] costs, int coins) {
int[] s = costs.clone();
Arrays.sort(s);
int bought = 0, left = coins;
for (int price : s) {
if (price > left) break;
left -= price;
bought++;
}
return bought;
}C++
int maxIceCream(vector<int>& costs, int coins) {
vector<int> s = costs;
sort(s.begin(), s.end());
int bought = 0, left = coins;
for (int price : s) {
if (price > left) break;
left -= price;
bought++;
}
return bought;
}JavaScript
var maxIceCream = function(costs, coins) {
const sorted = costs.slice().sort(function(a, b) { return a - b; });
let bought = 0, left = coins;
for (let i = 0; i < sorted.length; i++) {
if (sorted[i] > left) break;
left -= sorted[i];
bought++;
}
return bought;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms