Skip to main content
Talentd

Maximum Ice Cream Bars - Solution & Explanation

MediumArrayGreedySortingCounting Sort13 min readAsked at: Amazon, Microsoft, Google +2
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array costs where each value represents the price of an ice cream bar and an integer coins representing your budget. The goal is simple: buy the maximum number of bars without exceeding the available coins.

Approach 1: Greedy Algorithm using Sorting (Time: O(n log n), Space: O(1) or O(n) depending on sort)

The key observation is that cheaper bars should always be purchased first. If you spend coins on expensive bars early, you reduce the total number you can buy. Start by sorting the costs array in ascending order. Then iterate through the sorted prices and keep subtracting each cost from coins until you can no longer afford the next bar.

This works because a greedy choice—always picking the lowest cost—maximizes the count of items purchased. The algorithm performs a single pass after sorting, making it efficient and easy to implement. This approach directly uses concepts from greedy algorithms and sorting, which frequently appear together in optimization problems.

Approach 2: Counting Sort Optimization (Time: O(n + maxCost), Space: O(maxCost))

The sorting step can be avoided when the price range is reasonably bounded. Instead of sorting the entire array, build a frequency array where each index represents a price and the value represents how many bars have that price. This technique is essentially counting sort.

Once the frequency table is built, iterate from the smallest price upward. For each price p, determine how many bars you can afford: min(freq[p], coins // p). Deduct the corresponding cost from coins and update the purchased count. Because prices are processed in ascending order, you still maintain the greedy property without performing a full comparison-based sort.

This approach runs in linear time relative to the number of bars plus the maximum cost value. It is particularly useful when max(costs) is small compared to n log n, making it faster than traditional sorting.

Recommended for interviews: The sorting-based greedy solution is what most interviewers expect first. It clearly demonstrates recognition of the greedy pattern and produces a clean O(n log n) solution. Mentioning the counting sort optimization shows deeper understanding of algorithmic tradeoffs and when specialized linear-time techniques outperform comparison sorting.

Approach 1: Approach 1: Greedy Algorithm using Sorting

This approach involves sorting the array of costs to ensure the boy buys the cheapest available ice cream bars first. After sorting, iterate through the list and keep buying bars until you run out of coins.

Steps involve:

  • Sort the array of costs.
  • Iterate through the sorted costs array, and for each cost, check if it can be bought with the remaining coins.
  • Accumulate the cost and increase the count if it can be bought, otherwise break out of the loop.

This C program sorts the costs array using qsort and calculates the maximum number of ice creams that can be bought while iterating through the sorted array. It returns the count of ice creams the boy can afford.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1), as no additional space is required beyond the input.

Try this approach in the editor →

Approach 2: Approach 2: Counting Sort Optimization

This solution uses a variation of counting sort suitable for this specific problem due to the constraint that costs[i] <= 100,000.

Steps involve:

  • Using a frequency array to count occurrences of prices in the costs array.
  • Iterate over the frequency array, and decrement coins while counting how many ice creams can be bought at each price using the accumulated frequency.

This Python solution uses a frequency array to store the number of each cost. By iterating over these costs in order (with known max cost), it calculates how many bars of each cost can be purchased and subtracts the respective cost from the available coins, tallying the total ice creams bought.

Code

Python

Python

Complexity

Time Complexity: O(n + max(costs)), where max(costs) could be up to 100,000.
Space Complexity: O(max(costs)), because of the frequency array used.

Try this approach in the editor →

Approach 3: Greedy + Sorting

To buy as many ice creams as possible, and they can be purchased in any order, we should prioritize choosing ice creams with lower prices.

Sort the costs array, and then start buying from the ice cream with the lowest price, one by one, until it is no longer possible to buy, and return the number of ice creams that can be bought.

The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the costs array.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy Algorithm using Sorting

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1), as no additional space is required beyond the input.

Approach 2: Counting Sort Optimization

Time Complexity: O(n + max(costs)), where max(costs) could be up to 100,000.
Space Complexity: O(max(costs)), because of the frequency array used.

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with SortingO(n log n)O(1) to O(n)General case; simplest and most common interview solution
Counting Sort OptimizationO(n + maxCost)O(maxCost)When cost values are bounded and you want linear-time performance

Video Solution

Leetcode# 1833. Maximum Ice Cream Bars || Code + Explanation + Example Walkthrough • Code with Alisha • 3,048 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Ice Cream Bars easy or hard?
Maximum Ice Cream Bars is generally considered an easy-to-medium greedy problem. The core idea—buy the cheapest items first—is straightforward, but recognizing the counting sort optimization requires deeper algorithm knowledge.
How to solve Maximum Ice Cream Bars in O(n)?
Use a counting sort technique. Build a frequency array where each index represents a cost value and stores how many bars have that price. Iterate from the smallest price upward and buy as many as possible using coins. This avoids comparison sorting and runs in O(n + maxCost).
What is the best approach for Maximum Ice Cream Bars?
The most common solution uses a greedy strategy with sorting. Sort the costs array in ascending order and keep buying the cheapest bars until you run out of coins. This approach runs in O(n log n) time due to sorting and guarantees the maximum number of purchases.
Is Maximum Ice Cream Bars asked at Google/Amazon/Meta?
Maximum Ice Cream Bars is a common greedy-style interview problem and variations of it appear in interviews at large tech companies including Amazon and Google. The problem tests understanding of greedy decisions, sorting, and optimization techniques like counting sort.
What data structure is used in Maximum Ice Cream Bars?
The basic solution primarily uses arrays and sorting. The optimized version uses a frequency array (counting array) to simulate counting sort. Both rely on greedy iteration from the smallest cost to the largest.
What is the time complexity of Maximum Ice Cream Bars?
The standard greedy solution runs in O(n log n) time because the costs array must be sorted. After sorting, a single linear pass determines how many bars can be purchased. A counting sort optimization can reduce the time complexity to O(n + maxCost).
Maximum Ice Cream Bars Python or Java solution approach?
Both Python and Java implementations typically sort the costs array and iterate while subtracting from the coin budget. Python uses built-in sort and a loop, while Java uses Arrays.sort followed by a linear traversal. The logic remains identical across languages.

Ready to solve this problem?

Practice Maximum Ice Cream Bars with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays