Maximum Ice Cream Bars — Editorial

Opening the reading…

Intuitionwhy the cheapest available bar must be bought first

To maximize the number of bars, you should spend coins on the smallest prices first. If a purchase includes a bar costing more than another bar you skipped, exchanging those two choices never increases the spending and may leave more coins available. Repeating that exchange produces an optimal plan whose prices are in nondecreasing order.

After the prices are ordered, scan from cheapest to most expensive. Buy every bar you can afford, subtracting its price from coins. The first price you cannot afford ends the process: every later bar costs at least as much, so none of them can be bought either. The only remaining question is how to create this order using counting sort.

Frequency buckets replace comparison sorting while preserving the cheapest-first order.

Approachcount prices, then consume buckets from left to right

Find the largest price and create a frequency array with one slot for every price from 0 through that maximum, because counting sort needs a valid bucket for each possible array index.

Count how many bars have each price, because equal prices can then be processed together without comparing or rearranging individual bars.

Scan prices from 1 through the largest price, because this visits every distinct price in ascending order and therefore preserves the greedy cheapest-first strategy.

For the current price, buy as many bars from its bucket as the remaining coins allow, because each purchase has the same cost and every affordable purchase increases the answer by one.

Subtract the current price and increment the answer for every purchase, because the remaining budget and the number of bars must both reflect each accepted bar.

Stop as soon as the current price is greater than the remaining coins, because all later prices are at least as large and cannot be affordable; continuing would only inspect impossible purchases.

Return the answer after the scan, because it counts exactly the bars selected by the optimal cheapest-first order.

Complexitylinear in the input and the price range

MEASURE	BOUND	WHY
Time	O(n + M)	Finding the maximum and filling the frequency array each inspect the n input prices. The bucket scan visits each price from 1 through M once, and each bar is removed from its bucket at most once, so no bar or bucket is processed repeatedly beyond these totals.
Space	O(M) extra	The frequency array has M + 1 entries. The returned count is a scalar, so there is no output storage to exclude; the working memory is O(M), which reaches its worst shape when the largest price is 100000 even if many prices are absent.

M is the largest price in costs; under the stated limits, M is at most 100000.

Annotated solutionC++ - counting sort with grouped purchases

CPPCount each price, then buy the affordable portion of each bucket in ascending price order.

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        int maxCost = *max_element(costs.begin(), costs.end());
        vector<int> frequency(maxCost + 1, 0);

        for (int cost : costs) {
            frequency[cost]++;
        }

        int bought = 0;
        for (int cost = 1; cost <= maxCost; cost++) {
            if (coins < cost) {
                break;
            }

            int canBuy = min(frequency[cost], coins / cost);
            coins -= canBuy * cost;
            bought += canBuy;
        }

        return bought;
    }
};

The expression coins / cost tells you how many bars at this price the budget can pay for, while frequency[cost] limits that number to the bars that actually exist. Taking the minimum consumes an entire affordable group at once. The break is safe because the scan is already sorted by price: if cost is too large now, every later bucket is at least as expensive.