Scale Engineer

Maximum Ice Cream Bars

Med
#1675Time: O(n log n), where n is the number of ice cream bars. The dominant operation is sorting the `costs` array. The subsequent iteration takes O(n) time.Space: O(log n) to O(n), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort which has an average space complexity of O(log n) for the recursion stack.
Patterns
Greedy
Algorithms
SortingCounting Sort
Data structures
Array

Prompt

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 == n
  • 1 <= n <= 105
  • 1 <= costs[i] <= 105
  • 1 <= coins <= 108

Approaches

2 approaches with complexity analysis and trade-offs.

The core idea is that to maximize the number of ice cream bars, we should always prioritize buying the cheapest ones first. This is a classic greedy strategy. By sorting the costs in ascending order, we can iterate through them and buy each one as long as we have enough coins. This ensures that for a given number of bars, the total cost is minimized, thus allowing us to buy the maximum possible number of bars.

Algorithm

  • Sort the costs array in non-decreasing order. This places the cheapest ice cream bars first.
  • Initialize a counter for the number of ice cream bars bought, count, to 0.
  • Iterate through the sorted costs array from the beginning.
  • For each cost, check if the boy has enough coins to buy it (coins >= cost).
  • If he can afford it, subtract the cost from his coins and increment the count.
  • If he cannot afford it (coins < cost), it means he also cannot afford any of the subsequent, more expensive bars. Therefore, we can stop the process and break the loop.
  • Finally, return the total count.

Walkthrough

The algorithm follows a greedy strategy:

  • Sort the costs array in non-decreasing order. This places the cheapest ice cream bars first.
  • Initialize a counter for the number of ice cream bars bought, count, to 0.
  • Iterate through the sorted costs array from the beginning.
  • For each cost, check if the boy has enough coins to buy it (coins >= cost).
  • If he can afford it, subtract the cost from his coins and increment the count.
  • If he cannot afford it (coins < cost), it means he also cannot afford any of the subsequent, more expensive bars. Therefore, we can stop the process and break the loop.
  • Finally, return the total count.
import java.util.Arrays; class Solution {    public int maxIceCream(int[] costs, int coins) {        // Sort the costs in ascending order        Arrays.sort(costs);         int count = 0;        // Iterate through the sorted costs        for (int cost : costs) {            // If we can afford the current ice cream bar            if (coins >= cost) {                coins -= cost;                count++;            } else {                // If we can't afford this one, we can't afford any more expensive ones                break;            }        }        return count;    }}

Complexity

Time

O(n log n), where n is the number of ice cream bars. The dominant operation is sorting the `costs` array. The subsequent iteration takes O(n) time.

Space

O(log n) to O(n), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort which has an average space complexity of O(log n) for the recursion stack.

Trade-offs

Pros

  • Simple and intuitive to implement.

  • Works for any range of costs, not just limited ones.

Cons

  • Not the most efficient solution, as sorting takes O(n log n) time.

  • Does not meet the problem's specific requirement of using counting sort, if that is a strict condition.

Solutions

class Solution {public  int maxIceCream(int[] costs, int coins) {    Arrays.sort(costs);    int n = costs.length;    for (int i = 0; i < n; ++i) {      if (coins < costs[i]) {        return i;      }      coins -= costs[i];    }    return n;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem