💬 Discord
Sign In
NeetCode #768LC-1196EasyGreedy
← Back to All Problems

#768 · #1196 · How Many Apples Can You Put into the Basket(最多可以买到的苹果数量)

📌 Problem Statement & Constraints

You are given an array weight where weight[i] is the weight of the i-th apple. A basket can hold at most 5000 units. Return the maximum number of apples you can put in the basket. Constraints: 1 <= weight.length <= 10^3, 1 <= weight[i] <= 10^3.

💡 Core Algorithmic Approaches

  1. To maximise the count, take the lightest apples first.
  2. Sort the weights ascending and accumulate them.
  3. Stop as soon as adding the next apple would exceed 5000.
  4. The number of apples added so far is the answer.

💻 Benchmark Python3 Implementation

class Solution:
    def maxNumberOfApples(self, weight: List[int]) -> int:
        weight.sort()
        total = 0
        for i, w in enumerate(weight):
            total += w
            if total > 5000:
                return i               # i apples fit before this one
        return len(weight)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(1) beyond the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Using >= 5000 instead of > 5000: exactly 5000 is allowed, so the comparison must be strict.
  • Returning i + 1: the index i is the count of apples that fit before the overflowing one.
  • Taking the heaviest apples first: that minimises the count, not maximises it.
  • Forgetting that all apples may fit: the loop can finish without overflowing, so return the full length.