Maximum ice cream bars
January 6, 2023
greedy heapProblem URL: Maximum ice cream bars
We will sort the input costs
array, then iterate the array, if the current cost is less than coins
, we will update coins
to be coins-costs[i]
, and increment res
by 1.
class Solution:
def maxIceCream(self, costs: List[int], coins: int) -> int:
res = 0
for cost in sorted(costs):
if coins < cost:
break
res += 1
coins -= cost
return res
Time complexity: O(nlog(n))
Space complexity: O(1)
You can also solve this problem using heap. We will heapify the costs and pop the minimum cost from the heap if the current cost is less than coins
, we will update coins
to be coins-costs[i]
, and increment res
by 1.
class Solution:
def maxIceCream(self, costs: List[int], coins: int) -> int:
res = 0
heapq.heapify(costs)
while costs and coins >= costs[0]:
res += 1
coins -= heappop(costs)
return res
Time complexity: O(nlog(n))
Space complexity: O(n)