LeetCode Solutions Blog

How Many Apples Can You Put into the Basket

Number: 1141

Difficulty: Easy

Paid? Yes

Problem Description

Given an array of apple weights, determine the maximum number of apples that can be put into a basket such that their total weight does not exceed 5000 units.

Key Insights

Sort the apple weights in non-decreasing order.
Pick apples from the lightest until adding another apple would exceed the basket's capacity.
Using a greedy approach guarantees maximizing the count.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(1) if sorting is done in-place (or O(n) depending on the sorting algorithm implementation).

Solution

We first sort the array of weights so that we can add the lightest apples first. This is based on the greedy approach where adding smaller weights maximizes the count before reaching the capacity limit of 5000. We then iterate through the sorted array, keeping a cumulative sum of weights and a counter of the apples added. If adding the next apple exceeds the capacity, we stop and return the count. This method ensures that we have the maximum number of apples without overshooting the weight limit.

Code Solutions

# Function to compute maximum number of apples that can be added to the basket.
def max_apple_count(weight):
    # First, sort the list of weights in non-decreasing order.
    weight.sort()
    current_weight = 0  # Variable to track the current total weight in the basket.
    count = 0  # Variable to count the number of apples added.
    
    # Iterate over each apple's weight after sorting.
    for w in weight:
        # Check if adding this apple exceeds the basket's capacity.
        if current_weight + w > 5000:
            break  # Stop the loop if capacity would be exceeded.
        # Add the weight to the current total and increment the count.
        current_weight += w
        count += 1
        
    return count  # Return the maximum number of apples that can be added.

# Example test cases
print(max_apple_count([100,200,150,1000]))  # Expected output: 4
print(max_apple_count([900,950,800,1000,700,800]))  # Expected output: 5