Leetcode

1196. How Many Apples Can You Put into the Basket

You have some apples, where arr[i] is the weight of the i-th apple. You also have a basket that can carry up to 5000 units of weight.

Return the maximum number of apples you can put in the basket.

Example 1:

Input: arr = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

Example 2:

Input: arr = [900,950,800,1000,700,800]
Output: 5
Explanation: The sum of weights of the 6 apples exceeds 5000 so we choose any 5 of them.

Constraints:

  • 1 <= arr.length <= 10^3
  • 1 <= arr[i] <= 10^3

Solution:

# min-heapclass Solution:
def maxNumberOfApples(self, arr: List[int]) -> int:
heapq.heapify(arr)
apples = units = 0
# arr[0] always represents the smallest element in the min-heap
while arr and units + arr[0] <= 5000:
units += heapq.heappop(arr)
apples += 1
return apples
TC: O(N + k*longN),
# k is the number of apples would put in the basket
SC: O(1)# sortclass Solution:
def maxNumberOfApples(self, arr: List[int]) -> int:
arr.sort()
apples = units = 0
for _, weight in enumerate(arr):
units += weight
if units > 5000:
break
apples += 1
return apples
TC: O(nlogn) # becoz of sorting
SC: O(1)

Link

--

--

--

My homepage to record my thought processes for solving SQL and Algorithm questions

Recommended from Medium

Announcing ‘Woof’, a pure Scala 3 logging library

Using reflection in Golang

Architect is a team activity, not a person

AuroraFS

How to read an Excel File in Java Selenium projects

WordPress LMS: the good, the bad and the ugly (part I)

Young Coder’s Best of Summer 2021

TypeScript is Dying

Illustration of a man holding a lecture about programming languages.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jen-Li Chen

Jen-Li Chen

In love with telling stories with data

More from Medium

[Leetcode 525] Contiguous Array

Leetcode Q227. Basic Calculator II (Q219)

Solving The Coding Question From Amazon Interview

Linked List | LeetCode Top Interview Questions