Problem Description

You're given a scenario where a boy wants to buy ice cream bars on a hot summer day. There are n ice cream bars available at the store, each with a different price. You have an array costs of length n, where costs[i] represents the price of the i-th ice cream bar in coins.

The boy starts with a certain number of coins to spend, and his goal is to buy the maximum number of ice cream bars possible with the money he has. The key point is that he can purchase the ice cream bars in any order he wants.

Your task is to find and return the maximum number of ice cream bars the boy can buy with his available coins.

For example, if costs = [1, 3, 2, 4, 1] and coins = 7, the boy could buy ice cream bars costing 1, 1, 2, and 3 coins (total = 7 coins), giving him 4 ice cream bars in total.

The solution uses a greedy approach: to maximize the number of ice creams purchased, we should buy the cheapest ones first. By sorting the costs array in ascending order and then buying ice creams one by one starting from the cheapest until we run out of money, we can determine the maximum number of ice creams that can be bought.

The algorithm sorts the costs, then iterates through them, subtracting each cost from the available coins. When we encounter an ice cream that costs more than our remaining coins, we stop and return the count of ice creams bought so far. If we can afford all ice creams, we return the total length of the array.

Intuition

When we want to maximize the quantity of items we can buy with a fixed budget, the natural strategy is to prioritize cheaper items first. Think about it like shopping with limited money - if you want to buy as many items as possible, you'd pick the cheapest ones first.

This is a classic greedy problem. The key insight is that since we can buy ice creams in any order and our goal is to maximize the count (not the total value or any other metric), we should always choose the least expensive options available.

Why does this greedy approach work? Consider any optimal solution where we bought k ice creams. If we didn't buy them in order from cheapest to most expensive, we could swap a more expensive ice cream we bought with a cheaper one we didn't buy. This swap would either:

1. Allow us to buy the same number of ice creams with money left over
2. Allow us to potentially buy even more ice creams with the saved money

Therefore, sorting the costs and buying from cheapest to most expensive guarantees we get the maximum count.

The implementation becomes straightforward: sort the costs array, then iterate through it, keeping track of our remaining coins. We keep buying ice creams (subtracting their cost from our coins) until we encounter one we can't afford. The number of ice creams we've bought at that point is our answer. If we can afford all of them, we return the total count.

Learn more about Greedy and Sorting patterns.

Solution Approach

The solution implements a greedy algorithm with sorting to maximize the number of ice creams purchased.

Step 1: Sort the costs array

costs.sort()

We sort the costs array in ascending order. This ensures we can process ice creams from cheapest to most expensive. Python's built-in sort() uses Timsort algorithm with time complexity O(n log n).

Step 2: Iterate and buy ice creams greedily

for i, c in enumerate(costs):
    if coins < c:
        return i
    coins -= c

We iterate through the sorted costs using enumerate() to keep track of both the index i and the cost c:

• For each ice cream, we check if we have enough coins (coins < c)
• If we don't have enough coins, we immediately return i, which represents the number of ice creams bought so far
• If we have enough coins, we buy the ice cream by subtracting its cost from our remaining coins (coins -= c)

Step 3: Handle the case where all ice creams can be bought

return len(costs)

If the loop completes without returning early, it means we had enough coins to buy all ice creams. In this case, we return the total length of the costs array.

Time Complexity: O(n log n) due to sorting, where n is the number of ice creams.

Space Complexity: O(1) if we don't count the space used by the sorting algorithm (which is typically O(log n) for the recursion stack in Python's Timsort).

The beauty of this approach is its simplicity - by sorting first and then greedily selecting from the cheapest options, we guarantee the maximum number of purchases without needing complex data structures or dynamic programming.

Example Walkthrough

Let's walk through a concrete example to see how the greedy approach works.

Example: costs = [1, 6, 3, 1, 2, 5] and coins = 7

Step 1: Sort the costs array After sorting in ascending order:

costs = [1, 1, 2, 3, 5, 6]

Step 2: Buy ice creams greedily

Let's trace through each iteration:

• Iteration 0:

  • Current ice cream cost: 1
  • Remaining coins: 7
  • Can we afford it? Yes (7 ≥ 1)
  • Buy it! Coins left: 7 - 1 = 6
  • Ice creams bought: 1

• Iteration 1:

  • Current ice cream cost: 1
  • Remaining coins: 6
  • Can we afford it? Yes (6 ≥ 1)
  • Buy it! Coins left: 6 - 1 = 5
  • Ice creams bought: 2

• Iteration 2:

  • Current ice cream cost: 2
  • Remaining coins: 5
  • Can we afford it? Yes (5 ≥ 2)
  • Buy it! Coins left: 5 - 2 = 3
  • Ice creams bought: 3

• Iteration 3:

  • Current ice cream cost: 3
  • Remaining coins: 3
  • Can we afford it? Yes (3 ≥ 3)
  • Buy it! Coins left: 3 - 3 = 0
  • Ice creams bought: 4

• Iteration 4:

  • Current ice cream cost: 5
  • Remaining coins: 0
  • Can we afford it? No (0 < 5)
  • Stop and return 4

Result: The maximum number of ice creams we can buy is 4.

We bought ice creams costing [1, 1, 2, 3] for a total of 7 coins. Notice how by choosing the cheapest options first, we maximized our quantity. If we had bought the expensive ice cream costing 6 coins first, we could only have afforded 2 ice creams total (the 6-coin one and a 1-coin one).

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the costs array. This is dominated by the sorting operation costs.sort(), which uses Python's Timsort algorithm with O(n × log n) complexity in the average and worst cases. The subsequent iteration through the sorted array takes O(n) time, but this is absorbed by the larger sorting complexity.

The space complexity is O(log n). While the sorting operation is performed in-place (modifying the original array), Python's Timsort algorithm requires O(log n) auxiliary space for its internal operations, specifically for maintaining the stack of pending runs during the merge process. The remaining operations use only O(1) additional space for variables like i, c, and the modified coins value.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Input Array

The current solution sorts the costs array in-place using costs.sort(), which permanently modifies the original input. This can be problematic if:

• The caller expects the original array to remain unchanged
• The same array is being used elsewhere in the program
• You need to preserve the original order for any reason

Solution: Create a copy of the array before sorting:

def maxIceCream(self, costs: List[int], coins: int) -> int:
    # Create a copy to avoid modifying the original array
    sorted_costs = sorted(costs)  # or costs.copy() then sort
  
    for index, cost in enumerate(sorted_costs):
        if coins < cost:
            return index
        coins -= cost
  
    return len(sorted_costs)

2. Integer Overflow in Other Languages

While Python handles large integers automatically, if implementing this in languages like Java or C++, you might face integer overflow when:

• The sum of costs becomes very large
• The coins value is near the maximum integer limit

Solution: Use appropriate data types (like long in Java) or add overflow checks:

def maxIceCream(self, costs: List[int], coins: int) -> int:
    if coins <= 0:  # Handle edge case
        return 0
  
    costs.sort()
    count = 0
  
    for cost in costs:
        if cost > coins:  # Check before subtraction
            break
        coins -= cost
        count += 1
  
    return count

3. Not Handling Edge Cases

The current solution doesn't explicitly handle edge cases like:

• Empty costs array
• coins = 0 or negative coins
• All ice creams cost more than available coins

Solution: Add explicit edge case handling:

def maxIceCream(self, costs: List[int], coins: int) -> int:
    # Handle edge cases
    if not costs or coins <= 0:
        return 0
  
    costs.sort()
  
    # Early return if cheapest ice cream is unaffordable
    if costs[0] > coins:
        return 0
  
    for index, cost in enumerate(costs):
        if coins < cost:
            return index
        coins -= cost
  
    return len(costs)

4. Using Wrong Variable in the Loop

A common mistake is accidentally using the wrong variable or forgetting to update the coins:

# WRONG: Forgetting to update coins
for i, c in enumerate(costs):
    if coins < c:
        return i
    # Missing: coins -= c

Solution: Always verify that you're:

• Updating the remaining coins after each purchase
• Using the correct variable names consistently
• Returning the right value (index vs count)