You have some apples and a basket that can carry up to 5000 units of weight.
Given an integer array weight where weight[i] is the weight of the ith apple, return the maximum number of apples you can put in the basket.
Example 1:
Input: weight = [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: weight = [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 <= weight.length <= 1031 <= weight[i] <= 103Problem Overview: You are given an array where each value represents the weight of an apple. A basket can carry at most 5000 weight units. The task is to determine the maximum number of apples you can put into the basket without exceeding the limit.
Approach 1: Greedy with Sorting (O(n log n) time, O(1) extra space)
The optimal strategy is greedy: always pick the lightest apples first. Sort the array in ascending order, then iterate through it while maintaining a running weight total. For each apple, add its weight to the sum if the basket capacity allows it. Once adding another apple would exceed 5000, stop. This works because choosing lighter apples first maximizes the number of apples you can include. Sorting dominates the cost at O(n log n), while the single pass afterward is O(n). This technique combines greedy decision making with sorting to guarantee the optimal count.
Approach 2: Greedy with Counting Buckets (O(n + W) time, O(W) space)
If apple weights fall within a limited range (as in the problem constraints), you can avoid comparison sorting. Build a frequency array where index i stores how many apples weigh i. Then iterate from the smallest weight upward, greedily taking as many apples of that weight as possible without exceeding the capacity. Each step updates the remaining basket capacity and increments the apple count. This approach runs in O(n + W) time where W is the maximum possible weight value, and uses O(W) space for the frequency array. It’s essentially a counting sort–style optimization applied to a greedy selection process over the array.
Recommended for interviews: The greedy approach with sorting is what most interviewers expect. It shows you recognize the key insight: maximizing the number of items under a weight constraint means selecting the smallest weights first. Explaining the greedy reasoning and implementing the sorted iteration demonstrates solid algorithmic thinking. Mentioning the counting optimization is a bonus when constraints make it viable.
To maximize the number of apples, we should try to minimize the weight of the apples. Therefore, we can sort the weights of the apples, and then put them into the basket in ascending order until the weight of the basket exceeds 5000. We then return the number of apples in the basket at this point.
If all the apples can be put into the basket, then we return the total number of apples.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of apples.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) | General solution when weights are unsorted and no assumptions about range |
| Greedy with Counting Buckets | O(n + W) | O(W) | When weight values are within a small bounded range and you want to avoid sorting |
LeetCode 1196: How Many Apples Can You Put into Basket - Interview Prep Ep 29 • Fisher Coder • 2,779 views views
Watch 5 more video solutions →Practice How Many Apples Can You Put into the Basket with our built-in code editor and test cases.
Practice on FleetCode