Leetcode 1833: Maximum Ice Cream Bars

Input: The input consists of an array `costs` of length `n`, where `costs[i]` is the price of the `i-th` ice cream bar, and an integer `coins` representing the total coins the boy has.

Example: costs = [2, 1, 3, 4, 2], coins = 6

Constraints:

• 1 <= costs.length <= 10^5

• 1 <= costs[i] <= 10^5

• 1 <= coins <= 10^8

Output: Return the maximum number of ice cream bars the boy can buy without exceeding his available coins.

Example: 3

Constraints:

• The output will be a non-negative integer indicating the maximum number of ice cream bars that can be bought.

Goal: Determine the maximum number of ice cream bars the boy can afford given his budget.

Steps:

• Sort the `costs` array in non-decreasing order.

• Iterate through the sorted `costs` array and keep track of the total cost and the number of bars purchased.

• Stop when the total cost exceeds the available `coins`.

Goal: The boy’s budget and the ice cream bar costs are subject to the constraints defined below.

Steps:

• 1 <= costs.length <= 10^5

• 1 <= costs[i] <= 10^5

• 1 <= coins <= 10^8

Assumptions:

• The input array `costs` will contain only valid integer values.

• The `coins` value is guaranteed to be within the specified range.

• Input: costs = [2, 1, 3, 4, 2], coins = 6

• Explanation: By sorting the costs to [1, 2, 2, 3, 4], the boy can afford 3 ice cream bars for a total of 1 + 2 + 2 = 5 coins, leaving him with enough coins to buy 3 bars.

• Input: costs = [5, 3, 8, 2], coins = 4

• Explanation: The boy can only afford the ice cream bar with the price of 2 coins. He can buy just one ice cream bar.

• Input: costs = [1, 1, 2, 3, 1], coins = 7

• Explanation: The boy can afford all 5 bars for a total price of 8 coins, so he can buy 5 ice cream bars.

Approach: To solve this problem, we will use a greedy approach by sorting the array and then iterating through it to select as many bars as the boy can afford.

Observations:

• Sorting the costs array will allow us to buy the cheapest ice cream bars first, maximizing the number of bars the boy can afford.

• We can implement this solution efficiently with a time complexity of O(n log n) due to the sorting step.

Steps:

• Sort the array `costs` in ascending order.

• Initialize a counter to keep track of the number of ice cream bars bought.

• Iterate through the sorted `costs` array, and for each price, check if the boy can afford it by comparing the total spent so far with his available coins.

• Return the number of ice cream bars the boy can afford.

Empty Inputs:

• The array `costs` will always contain at least one element.

Large Inputs:

• For large inputs, sorting the `costs` array will take O(n log n) time, which should be efficient enough within the problem's constraints.

Special Values:

• If the boy cannot afford any ice cream bars, the result will be 0.

Constraints:

• Ensure that the sorting and iteration steps are optimized for large inputs.

int maxIceCream(vector<int>& costs, int coins) {
    sort(costs.begin(), costs.end());
    int sum = 0;
    for(int i = 0; i < costs.size(); i++) {
        sum += costs[i];
        if(sum == coins)
            return i +1;
        if(sum > coins)
            return i;
    }
    return costs.size();
}

1 : Function Definition

int maxIceCream(vector<int>& costs, int coins) {

Defines the function `maxIceCream`, which takes a vector of ice cream costs (`costs`) and the total number of coins (`coins`) as input, and returns the maximum number of ice creams that can be bought.

2 : Sorting

    sort(costs.begin(), costs.end());

Sorts the `costs` vector in ascending order to prioritize buying cheaper ice creams first.

3 : Variable Initialization

    int sum = 0;

Initializes a variable `sum` to keep track of the total cost of ice creams bought so far.

4 : Loop Through Costs

    for(int i = 0; i < costs.size(); i++) {

Starts a loop to iterate through the sorted `costs` vector, with each iteration representing the purchase of one ice cream.

5 : Sum Calculation

        sum += costs[i];

Adds the cost of the current ice cream (`costs[i]`) to the running total (`sum`).

6 : Exact Match Check

        if(sum == coins)

Checks if the accumulated `sum` exactly matches the available `coins`.

7 : Return Exact Match

            return i + 1;

If the total cost matches the available coins, returns the current index plus one, representing the number of ice creams bought.

8 : Exceed Coins Check

        if(sum > coins)

Checks if the accumulated `sum` exceeds the available `coins`.

9 : Return Exceed Case

            return i;

If the total cost exceeds the available coins, returns the current index, which represents the maximum number of ice creams that can be bought.

10 : Return Total Ice Creams

    return costs.size();

If all ice creams can be bought without exceeding the available coins, returns the total number of ice creams.

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: The time complexity is dominated by the sorting step, which takes O(n log n) time.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the space required for sorting the array.

Leetcode 1833: Maximum Ice Cream Bars

Explore →