Code Implementation

class Solution:
    def maxIceCream(self, costs, coins):
        costs.sort()
        count = 0
        for price in costs:
            if coins >= price:
                coins -= price
                count += 1
            else:
                break
        return count
      

class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        sort(costs.begin(), costs.end());
        int count = 0;
        for (int price : costs) {
            if (coins >= price) {
                coins -= price;
                count++;
            } else {
                break;
            }
        }
        return count;
    }
};
      

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int count = 0;
        for (int price : costs) {
            if (coins >= price) {
                coins -= price;
                count++;
            } else {
                break;
            }
        }
        return count;
    }
}
      

var maxIceCream = function(costs, coins) {
    costs.sort((a, b) => a - b);
    let count = 0;
    for (let price of costs) {
        if (coins >= price) {
            coins -= price;
            count++;
        } else {
            break;
        }
    }
    return count;
};
      

Problem Description

You are given an array costs where each element represents the price of an ice cream bar, and an integer coins representing the total amount of money you have. Your task is to buy as many ice cream bars as possible using the coins you have. Each ice cream bar can be purchased at most once, and you cannot spend more coins than you possess. Return the maximum number of ice cream bars you can buy.

• You must not reuse or buy the same ice cream bar more than once.
• There is always a valid answer (it is possible to buy zero bars if you can't afford any).
• The solution should maximize the total number of bars bought, not the total cost spent.

Thought Process

At first glance, you might think about trying every possible combination of ice cream bars to see which set gives you the most bars without exceeding your coin limit. However, this brute-force approach is very inefficient, especially as the number of ice cream bars grows.

To optimize, consider what will let you buy the most bars: buying the cheapest ones first. If you always pick the least expensive bars, you'll be able to buy more before running out of coins. This leads to a greedy approach: sort the prices from lowest to highest, and keep buying until you can't afford the next one.

Solution Approach

• Step 1: Sort the costs array in ascending order. This lets you access the cheapest ice cream bars first.
• Step 2: Initialize a counter (e.g., count) to keep track of how many bars you have bought.
• Step 3: Iterate through the sorted costs array:
• For each price, check if you still have enough coins to buy it.
• If yes, subtract that price from coins and increment your counter.
• If not, stop the process — you can't afford any more bars.
• Step 4: Return the counter, which represents the maximum number of ice cream bars you can buy.

This greedy approach works because buying cheaper bars first always leaves you with more coins to potentially buy more bars, maximizing the count.

Example Walkthrough

Suppose costs = [1, 3, 2, 4, 1] and coins = 7.

1. Sort costs: [1, 1, 2, 3, 4]
2. Start with coins = 7 and count = 0.
3. First bar (cost 1): coins left = 6, count = 1
4. Second bar (cost 1): coins left = 5, count = 2
5. Third bar (cost 2): coins left = 3, count = 3
6. Fourth bar (cost 3): coins left = 0, count = 4
7. Fifth bar (cost 4): can't afford (coins = 0), so stop.

The final answer is 4, since you can buy 4 ice cream bars with 7 coins.

Time and Space Complexity

• Brute-force approach:
  • Would try all subsets of the ice cream bars, which is O(2ⁿ) time — extremely slow for large n.
  • Space complexity would also be high due to recursion or storing subsets.
• Optimized greedy approach (as above):
  • Sorting the costs array takes O(n log n) time.
  • The single pass through the array is O(n) time.
  • Total time complexity: O(n log n).
  • Space complexity: O(1) if sorting in-place, otherwise O(n) if a new array is created.

Summary

The key insight is to always buy the cheapest available ice cream bars first. By sorting the prices and purchasing in order, you maximize the number of bars you can buy with your coins. This greedy approach is simple, efficient, and easy to implement, making it an elegant solution to the problem.