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

Sorting Counting 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 i^th 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 <= 10⁵
1 <= costs[i] <= 10⁵
1 <= coins <= 10⁸

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.

1import java.util.Arrays;2 3class Solution {4    public int maxIceCream(int[] costs, int coins) {5        // Sort the costs in ascending order6        Arrays.sort(costs);7 8        int count = 0;9        // Iterate through the sorted costs10        for (int cost : costs) {11            // If we can afford the current ice cream bar12            if (coins >= cost) {13                coins -= cost;14                count++;15            } else {16                // If we can't afford this one, we can't afford any more expensive ones17                break;18            }19        }20        return count;21    }22}

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.

This approach also uses the same greedy strategy of buying the cheapest ice cream bars first. However, instead of a general-purpose comparison-based sort, it uses Counting Sort, which is more efficient for the given constraints. Since the costs are positive integers within a limited range (1 to 10^5), we can count the frequency of each cost and then iterate through the costs from cheapest to most expensive, buying as many as we can afford at each price point.

Algorithm

First, determine the range of costs. The maximum cost m can be found by iterating through the costs array or by using the problem's constraint (10^5).
Create a frequency array, costFrequency, of size m + 1. This array will store how many ice cream bars exist for each cost.
Populate the costFrequency array by iterating through the input costs array. For each cost, increment costFrequency[cost].
Initialize the number of bought ice creams, iceCreamCount, to 0.
Iterate through the possible costs from 1 to m.
For each cost:
- If coins < cost, we cannot afford even the cheapest remaining bar, so we break the loop.
- If there are bars at the current cost (costFrequency[cost] > 0), we determine how many we can buy.
- The number of bars to buy at this cost, countToBuy, is the minimum of the available bars (costFrequency[cost]) and the number we can afford with our remaining coins (coins / cost).
- Add countToBuy to iceCreamCount.
- Decrease coins by countToBuy * cost.
After the loop finishes, return iceCreamCount.

Walkthrough

This approach leverages counting sort for linear time complexity, which is optimal given the constraints on the cost values.

First, determine the range of costs. The maximum cost m can be found by iterating through the costs array or by using the problem's constraint (10^5).
Create a frequency array, costFrequency, of size m + 1. This array will store how many ice cream bars exist for each cost.
Populate the costFrequency array by iterating through the input costs array. For each cost, increment costFrequency[cost].
Initialize the number of bought ice creams, iceCreamCount, to 0.
Iterate through the possible costs from 1 to m.
For each cost:
- If coins < cost, we cannot afford even the cheapest remaining bar, so we break the loop.
- If there are bars at the current cost (costFrequency[cost] > 0), we determine how many we can buy.
- The number of bars to buy at this cost, countToBuy, is the minimum of the available bars (costFrequency[cost]) and the number we can afford with our remaining coins (coins / cost).
- Add countToBuy to iceCreamCount.
- Decrease coins by countToBuy * cost.
After the loop finishes, return iceCreamCount.

1class Solution {2    public int maxIceCream(int[] costs, int coins) {3        // Per constraints, max cost is 10^5. We can find the actual max for a tighter bound.4        int maxCost = 0;5        for (int cost : costs) {6            maxCost = Math.max(maxCost, cost);7        }8 9        if (maxCost == 0) return 0;10        11        int[] costFrequency = new int[maxCost + 1];12        for (int cost : costs) {13            costFrequency[cost]++;14        }15 16        int iceCreamCount = 0;17        for (int cost = 1; cost <= maxCost; cost++) {18            if (coins < cost) {19                break;20            }21            22            if (costFrequency[cost] == 0) {23                continue;24            }25 26            int countToBuy = Math.min(costFrequency[cost], coins / cost);27            28            coins -= countToBuy * cost;29            iceCreamCount += countToBuy;30        }31        return iceCreamCount;32    }33}

Complexity

Time

O(n + m), where n is the number of ice cream bars and m is the maximum possible cost. O(n) to build the frequency map, and O(m) to iterate through the possible costs. This is linear time and more efficient than O(n log n).

Space

O(m), where m is the maximum possible cost. We need an auxiliary array to store the frequency of each cost. Given the constraint `costs[i] <= 10^5`, this is a fixed amount of extra space.

Trade-offs

Pros

Highly efficient with linear time complexity.
Satisfies the problem's specific requirement to use counting sort.
Optimal solution for the given constraints.

Cons

Requires extra space proportional to the maximum cost, which might be large if the cost range is not bounded.
Less general than comparison-based sorting; only works well for integers in a limited range.

Solutions

Solution

1class Solution {2public3  int maxIceCream(int[] costs, int coins) {4    Arrays.sort(costs);5    int n = costs.length;6    for (int i = 0; i < n; ++i) {7      if (coins < costs[i]) {8        return i;9      }10      coins -= costs[i];11    }12    return n;13  }14}

1/** * @param {number[]} costs * @param {number} coins * @return {number} */ var maxIceCream =2  function (costs, coins) {3    costs.sort((a, b) => a - b);4    const n = costs.length;5    for (let i = 0; i < n; ++i) {6      if (coins < costs[i]) {7        return i;8      }9      coins -= costs[i];10    }11    return n;12  };

1class Solution {2public:3  int maxIceCream(vector<int> &costs, int coins) {4    sort(costs.begin(), costs.end());5    int n = costs.size();6    for (int i = 0; i < n; ++i) {7      if (coins < costs[i])8        return i;9      coins -= costs[i];10    }11    return n;12  }13};

1class Solution:2    def maxIceCream(self, costs: List[int], coins: int) -> int: costs . sort() for i, c in enumerate(costs): if coins < c: return i coins -= c return len(costs)

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 problem