[LeetCode] 1833. Maximum Ice Cream Bars (Medium/Python)

Maximum Ice Cream Bars - LeetCode

Above is the link to the problem.

 

Problem

There are n ice cream bars.

You are given an array "costs" of length n, where costs[i] is the price of the i th ice cream bar in coins.

The boy initially has "coins" to spend, and he wants to buy as many ice cream bars as possible. 

Return the maximum number of ice cream bars the boy can buy with "coins".

Note: The boy can buy the ice cream bars in any order.

 

Example

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.

 

At first, I tried to solve the problem using the min() function,

but when the min() included in the for loop,

the problem of time-out occurred when the list is long.

Therefore, the algorithm was implemented by sorting the list first in ascending order and then buying ice cream from lowest index.

 

Code

 

Explanation

When the list "costs" is sorted, we can count the number of ice cream that can buy using all of coins easily.

Just repeat substraction costs[i] to coins from minimum index i until the coin is not sufficient to buy a new cheapest ice cream.

This code gets the top 1.25% of time complexity and uses 27.9MB of memory.