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

Squirrel Weekly (08/12) 🐿️

Backtracking Algorithm

Do natural pay over.

Engineering

Using an Amazon Simple Queue Service to invoke a Lambda function on LocalStack

Do’s and Dont’s Of Coding For Beginners As Well As Advanced Coders

My First HTML & CSS Challenge

Algorithms and Data Structures Part VIII

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
Isabelle

Isabelle

In love with telling stories with data

More from Medium

Leetcode Blind 75 Practice-Maximum Subarray

Leetcode 334. Increasing Triplet Subsequence

1155. Number of Dice Rolls With Target Sum

Linked List | LeetCode Top Interview Questions