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.

Description Hints 3 Solution Video 5:33

1196. How Many Apples Can You Put into the Basket

Easy67.0% acceptance1 companyPremium elsewhere, free here

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 i^th 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 <= 10³
1 <= weight[i] <= 10³

Asked at 1 company

Virtu Financial

Topics

Hints open one at a time

Hint 1

What if you think in a greedy approach?

Hint 2

The best apple to take in one step is the one with the smallest weight.

Hint 3

Sort the array and take apples with smaller weight first.

5:33

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[100,200,150,1000]

Input

[900,950,800,1000,700,800]

Your code is saved on this device.Solution