Domain 1EasyCORE

How Many Apples Can You Put into the Basket

The problem asks us to determine the maximum number of apples that can be placed into a basket with a weight capacity of 5000 units. The input is an array `arr` where each element represents the weight of an apple. The output should be the count of apples that can fit in the basket without exceeding its weight limit.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Greedy

1196. How Many Apples Can You Put into the Basket

Model: qwen2.5-coder:14b
Topics: Greedy
FAANG asked: 0
Acceptance rate: 68.3%


Problem Breakdown

The problem asks us to determine the maximum number of apples that can be placed into a basket with a weight capacity of 5000 units. The input is an array arr where each element represents the weight of an apple. The output should be the count of apples that can fit in the basket without exceeding its weight limit.

Inputs:

  • An array arr of integers representing the weights of apples.
  • A constant integer 5000 representing the maximum weight capacity of the basket.

Outputs:

  • An integer representing the maximum number of apples that can be placed into the basket.

Implicit Constraints or Tricky Edge Cases:

  • If the total weight of all apples is less than or equal to 5000, return the length of the array.
  • If no apples can fit in the basket (all weights are greater than 5000), return 0.
  • The array can be empty, but since 1 <= arr.length <= 10^3, this is not a practical edge case to consider.

Intuition

A brute-force approach would involve checking all possible combinations of apples and selecting the one with the maximum count that does not exceed the weight limit. However, this approach is computationally expensive with a time complexity of O(2^n), where n is the number of apples, making it impractical for larger inputs.

The key insight to improve the solution is to sort the array of apple weights and then iteratively add the lightest apples first until adding another apple would exceed the weight limit. This greedy approach ensures that we maximize the number of apples in the basket without exceeding its capacity.

Approach

  1. Sort the Array: Begin by sorting the array of apple weights in ascending order. This allows us to consider the lightest apples first, maximizing the number of apples we can fit.
  2. Initialize Variables: Use a variable current_weight to keep track of the total weight of apples currently in the basket and another variable count to count the number of apples added.
  3. Iterate Through the Sorted Array: For each apple in the sorted array, add its weight to current_weight. If adding this apple exceeds the weight limit (5000), break out of the loop as no more apples can be added.
  4. Increment Count: Each time an apple is successfully added to the basket, increment the count.
  5. Return the Count: After iterating through the array or breaking out of the loop, return the value of count.

Complexity Analysis

  • Time Complexity: O(n log n) due to the sorting step, where n is the number of apples in the input array.
  • Space Complexity: O(1) as we are using a constant amount of extra space for variables regardless of the input size.

Solution

def maxNumberOfApples(arr):
    arr.sort()  # Sort the array of apple weights
    current_weight = 0  # Initialize the current weight in the basket
    count = 0  # Initialize the count of apples added to the basket
    
    for weight in arr:
        if current_weight + weight > 5000:  # Check if adding this apple exceeds the weight limit
            break
        current_weight += weight  # Add the apple's weight to the current weight
        count += 1  # Increment the count of apples added
    
    return count  # Return the maximum number of apples that can be added

# Example usage:
print(maxNumberOfApples([100, 200, 150, 1000]))  # Output: 4
print(maxNumberOfApples([900, 950, 800, 1000, 700, 800]))  # Output: 5

Edge Cases Handled

  • All apples fit in the basket: If the total weight of all apples is less than or equal to 5000, the function will return the length of the array.
  • No apples fit in the basket: If all apple weights are greater than 5000, the loop will not execute, and the function will return 0.
  • Empty input array: Although the problem constraints specify that 1 <= arr.length <= 10^3, if the array were empty, the function would correctly return 0.