Maximum Ice Cream Bars - Leetcode Solution

Problem Statement:

You have n ice cream bars, and each bar has a flavor that is described by an integer value arr[i].

You have a budget of coins to spend, where each ice cream bar costs coins[i] coins.

You can buy any number of ice cream bars, but you are only allowed to spend the entire budget.

Return the maximum number of ice cream bars you can buy.

Solution:

The problem can be solved by first sorting the array of ice cream flavors (arr) in ascending order. Then iterating through the sorted array and buying as many ice cream bars as possible with the remaining budget.

We can start by sorting the array arr in ascending order. We do not need to sort the array of coins as well, since the price of ice cream bars corresponds to their respective indices in the array. As such, we can directly access the prices of each ice cream flavor using their indices.

Next, we initialize a variable totalBars to 0 to keep track of the total number of ice cream bars we can buy. We also initialize a variable budget to the given budget of coins.

We then iterate through the sorted array of ice cream flavors, and for each flavor, we check whether we have enough budget to buy it. If we do, we decrement the budget by the price of the ice cream bar, and increment totalBars by 1. We continue this process until we run out of budget or have iterated through all the ice cream flavors.

Once we have iterated through all the ice cream flavors or have run out of budget, we return the total number of ice cream bars we have bought.

Here is the code implementation of the above approach:

def maxIceCream(self, arr: List[int], coins: int) -> int:
        arr.sort() # sort the array of ice cream flavors in ascending order
        totalBars = 0 # initialize variable to keep track of total number of ice cream bars bought
        budget = coins # initialize variable to keep track of remaining budget
        for i in range(len(arr)):
            if arr[i] <= budget: # check if we have enough budget to buy this ice cream flavor
                budget -= arr[i] # decrement budget by the price of the ice cream bar
                totalBars += 1 # increment totalBars by 1
            else:
                break # if we do not have enough budget to buy this ice cream flavor, break out of the loop
        return totalBars # return the total number of ice cream bars bought

Time Complexity:

The time complexity of the above approach is O(nlogn + n), where n is the length of the input array of ice cream flavors. This is because the sorting operation takes O(nlogn) time, and the subsequent iteration through the sorted array takes O(n) time.

Space Complexity:

The space complexity of the above approach is O(1), since we are only using a constant amount of extra space to store variables.

1