LeetCode 1833: Maximum Ice Cream Bars

Explanation:

To solve this problem, we can use counting sort to efficiently find the maximum number of ice cream bars the boy can buy within the given budget. We will first count the frequency of each ice cream bar's cost and then iterate through the sorted costs array to determine how many ice cream bars the boy can buy until he runs out of coins.

• Perform counting sort on the costs array to get a sorted array.
• Iterate through the sorted array, deducting the cost of each ice cream bar from the available coins until the boy cannot afford the next ice cream bar.
• Return the count of ice cream bars bought.

Time Complexity: O(n)
Space Complexity: O(max(costs))

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int[] count = new int[100001]; // Considering the constraints
        for (int cost : costs) {
            count[cost]++;
        }
        
        int numIceCreams = 0;
        for (int i = 1; i < count.length && coins > 0; i++) {
            int iceCreamsToBuy = Math.min(count[i], coins / i);
            numIceCreams += iceCreamsToBuy;
            coins -= iceCreamsToBuy * i;
        }
        
        return numIceCreams;
    }
}