# Maximum Ice Cream Bars
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-ice-cream-bars)
Canonical: https://scaleengineer.com/dsa/problems/maximum-ice-cream-bars
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Counting Sort](https://scaleengineer.com/algorithms/counting-sort)
**Data structures:** Array
---
## Problem
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
## Greedy Approach with Sorting
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Greedy Approach with Counting Sort
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.
**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.
**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.
### Explanation
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`.

```java
class Solution {
    public int maxIceCream(int[] costs, int coins) {
        // Per constraints, max cost is 10^5. We can find the actual max for a tighter bound.
        int maxCost = 0;
        for (int cost : costs) {
            maxCost = Math.max(maxCost, cost);
        }

        if (maxCost == 0) return 0;
        
        int[] costFrequency = new int[maxCost + 1];
        for (int cost : costs) {
            costFrequency[cost]++;
        }

        int iceCreamCount = 0;
        for (int cost = 1; cost <= maxCost; cost++) {
            if (coins < cost) {
                break;
            }
            
            if (costFrequency[cost] == 0) {
                continue;
            }

            int countToBuy = Math.min(costFrequency[cost], coins / cost);
            
            coins -= countToBuy * cost;
            iceCreamCount += countToBuy;
        }
        return iceCreamCount;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} costs * @param {number} coins * @return {number} */ var maxIceCream =
  function (costs, coins) {
    costs.sort((a, b) => a - b);
    const n = costs.length;
    for (let i = 0; i < n; ++i) {
      if (coins < costs[i]) {
        return i;
      }
      coins -= costs[i];
    }
    return n;
  };

```

### CPP

```cpp
class Solution {
public:
  int maxIceCream(vector<int> &costs, int coins) {
    sort(costs.begin(), costs.end());
    int n = costs.size();
    for (int i = 0; i < n; ++i) {
      if (coins < costs[i])
        return i;
      coins -= costs[i];
    }
    return n;
  }
};

```

### Python

```python
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)

```