Watch 6 video solutions for How Many Apples Can You Put into the Basket, a easy level problem involving Array, Greedy, Sorting. This walkthrough by Fisher Coder has 2,779 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |