Maximum Ice Cream Bars

Medium
349.

Maximum Ice Cream Bars

Maximum Ice Cream Bars is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.

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 <= 40
  • 1 <= costs[i] <= 1000
  • 1 <= coins <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} costs
 * @param {number} coins
 * @return {number}
 */
var maxIceCream = function(costs, coins) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 40
  • 1 <= costs[i] <= 1000
  • 1 <= coins <= 100000

Hints for Maximum Ice Cream Bars

  1. Hint 1

    Since every bar counts the same toward the answer, always buy the cheapest remaining one.

  2. Hint 2

    Sort ascending and spend until the next bar is unaffordable.

  3. 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

  1. Sort prices ascending.
  2. 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 bought

Java

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