< Back





1196. How Many Apples Can You Put into the Basket

We're given a list of weights corresponding to apples, and we're asked to pick as many apples as
possible, but our bag can fit at most 5000 units of weight for the apples. We use the regular greedy
approach, but instead of sorting the input or using a heap, we'll use counting sort.

We determine what the max weight is, and we count the frequency of each weight present in the input.
We maintain a running total to ensure we haven't exceeded the weight limit. From 0 to the max
weight, we'll inspect our frequency dictionary and pick as many apples as possible, ensuring we
don't exceed the weight limit.

If we can't pick any more apples, we terminate and return the number of apples we've picked. If we
can select from the current bucket of weight apples, we add the number of apples we've picked to our
answer and update our total weight.

The solution is as follows:


  from collections import Counter

  class Solution:
      def maxNumberOfApples(self, weight: List[int]) -> int:
          max_weight = max(weight) + 1
          count = Counter(weight)
          ans = total = 0

          for i in range(max_weight):
              if count.get(i, 0):
                  take = min(count[i], (5000 - total) // i)

                  if not take:
                      break

                  ans += take
                  total += take * i

          return ans


_ Time Complexity:

  O(n + w) - Where n is the length of the input list and w is the maximum weight of an apple.

_ Space Complexity:

  O(n) - Our dictionary of counts contains at most n elements.