Skip to main content
Talentd

How Many Apples Can You Put into the Basket - Solution & Explanation

EasyPremiumFree on FleetCodeArrayGreedySorting6 min readAsked at: Virtu
Practice this problem

Problem Statement

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 <= 103
  • 1 <= weight[i] <= 103

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with SortingO(n log n)O(1)General solution when weights are unsorted and no assumptions about range
Greedy with Counting BucketsO(n + W)O(W)When weight values are within a small bounded range and you want to avoid sorting

Video Solution

LeetCode 1196: How Many Apples Can You Put into Basket - Interview Prep Ep 29 • Fisher Coder • 2,795 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is How Many Apples Can You Put into the Basket easy or hard?
How Many Apples Can You Put into the Basket is classified as an Easy problem. The main challenge is recognizing the greedy insight that selecting the smallest weights first maximizes the number of apples that fit within the basket capacity.
How Many Apples Can You Put into the Basket Python/Java solution
The typical Python or Java solution sorts the weights array and iterates through it while maintaining a running total. Each apple is added if the cumulative weight stays within 5000. The loop stops once adding another apple would exceed the limit.
How to solve How Many Apples Can You Put into the Basket in O(n)?
An O(n) style solution can be achieved using a counting bucket approach when apple weights fall within a bounded range. Build a frequency array of weights, then iterate from the smallest weight upward while subtracting from the remaining basket capacity. This avoids comparison sorting and runs in O(n + W) time where W is the maximum weight value.
What is the best approach for How Many Apples Can You Put into the Basket?
The best approach is a greedy strategy combined with sorting. Sort the apple weights in ascending order and keep adding the smallest apples until the total weight reaches the basket limit of 5000. This ensures the maximum number of apples because lighter apples allow more items to fit within the capacity.
Is How Many Apples Can You Put into the Basket asked at Google/Amazon/Meta?
Greedy selection problems with capacity constraints are common in interviews at companies like Amazon and Google. While this exact problem may appear more frequently on practice platforms, the underlying pattern—sorting items and greedily filling capacity—is a common interview concept.
What data structure is used in How Many Apples Can You Put into the Basket?
The problem primarily uses arrays along with a greedy algorithm. In the standard approach, the array is sorted and iterated sequentially. An alternative approach uses a frequency array (counting bucket) to track how many apples exist for each weight value.
What is the time complexity of How Many Apples Can You Put into the Basket?
The standard greedy solution runs in O(n log n) time due to sorting the array of apple weights. After sorting, a single linear pass adds apples until the weight limit is reached, which takes O(n). Space complexity is O(1) if sorting is done in place.

Ready to solve this problem?

Practice How Many Apples Can You Put into the Basket with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays