#1833

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Ice Cream Bars

Maximize the number of ice cream bars a boy can buy by applying a greedy choice strategy based on cost sorting.

Problem Statement

A boy wants to buy as many ice cream bars as possible on a hot summer day. Each bar has a cost given in the array costs, and he has a limited number of coins.

He can purchase bars in any order, but the goal is to maximize the number of bars bought without exceeding his total coins. Determine the maximum bars he can purchase using an optimal strategy.

Examples

Example 1

Input: costs = [1,3,2,4,1], coins = 7

Output: 4

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

The boy cannot afford any of the ice cream bars.

Example 3

Input: costs = [1,6,3,1,2,5], coins = 20

Output: 6

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

Solution Approach

Sort Costs Ascending

Sort the array of ice cream bar costs from lowest to highest. This allows applying a greedy strategy by considering the cheapest bars first.

Greedy Purchase Loop

Iterate through the sorted costs and subtract each cost from coins if affordable. Stop when the next bar exceeds remaining coins, ensuring the invariant that coins are never overspent.

Counting Sort Optimization

For large n with bounded costs, use counting sort to avoid full comparison-based sorting. Iterate through the counts to purchase bars efficiently without breaking the greedy invariant.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) with standard sort, or O(n + maxCost) with counting sort. Space complexity is O(n) for sorting or O(maxCost) for counting array. Iteration is O(n) in all cases.

What Interviewers Usually Probe

Ask how to maximize purchases without overspending coins.
Check if candidate recognizes greedy choice invariant with costs.
Probe if counting sort can optimize large inputs efficiently.

Common Pitfalls or Variants

Common pitfalls

Failing to sort costs before greedy selection leads to suboptimal purchases.
Attempting to pick bars in arbitrary order can exceed coins early.
Ignoring large cost values and limits may cause inefficiency or overflow.

Follow-up variants

Compute maximum bars if each bar has a limit on quantity available.
Determine maximum bars with a dynamic coin replenishment after each purchase.
Maximize bars when only contiguous subarrays of costs can be purchased.

FAQ

What is the main strategy for Maximum Ice Cream Bars problem?

The key strategy is greedy selection: always buy the cheapest available ice cream bar first to maximize the total count.

Can this problem be optimized without full sorting?

Yes, using counting sort for bounded costs allows linear-time iteration to achieve the greedy selection efficiently.

What should I watch out for when implementing this solution?

Ensure costs are sorted or counted correctly, track coins carefully, and stop purchasing before exceeding coins.

How does the greedy choice invariant apply here?

The invariant ensures that buying cheaper bars first never reduces the total number of bars obtainable, preserving optimality.

Are there variations of Maximum Ice Cream Bars I should consider?

Variants include limits on bar quantities, dynamic coins, or constraints on purchasing contiguous subarrays.

terminal

Solution

Solution 1: Greedy + Sorting

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.

1

2

3

4

5

6

7

8

class Solution:
    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)

Continue Practicing

#2037 minimum number of moves to seat everyone #1838 frequency of the most frequent element #1846 maximum element after decreasing and rearranging