How Many Apples Can You Put Into The Basket - Leetcode Solution

Problem:

You have a basket that can carry up to 5000 apples, and you have a list of apples where the weight of the ith apple is apples[i].

Given an integer array apples of length n where apples[i] is the weight of the ith apple, return the maximum number of apples you can put in the basket.

Solution:

This is a simple problem that can be solved by iterating through the apples array and adding the weight of the apples to a variable until the weight exceeds the capacity of the basket (5000). At this point, we remove the last apple added to the basket and continue iterating until we reach the end of the array.

Python Code:

def maxNumberOfApples(apples: List[int]) -> int:
    apples.sort() # sort the apples by weight
    basket_weight = 0
    num_apples = 0

    for apple in apples:
        if basket_weight + apple <= 5000:
            basket_weight += apple
            num_apples += 1
        else:
            break

    return num_apples

Explanation:

First, we sort the apples by weight using the sort() function. This is done to ensure that we take the smallest apples first, which gives us the best chance of fitting more apples into the basket.

Next, we initialize the weight of the basket to 0, and the number of apples in the basket to 0.

We then loop through the sorted apples array. For each apple, we check if adding it to the basket would exceed the capacity of 5000. If it does not, we add the weight of the apple to the basket_weight variable and increment the num_apples variable by 1.

If adding the apple would exceed the capacity of the basket, we break out of the loop since we cannot add any more apples.

Finally, we return the num_apples variable, which is the maximum number of apples that we can put in the basket.

Time Complexity:

The time complexity of this solution is O(nlogn) since we use the sort() function to sort the apples array. The space complexity is O(1) since we only use a constant amount of extra space to store the basket weight and the number of apples in the basket.

Note: This problem could also be solved using a heap, which would make the time complexity O(nlogk) where k is the capacity of the basket. However, since the capacity is fixed at 5000, the difference in time complexity would not be significant for this problem.

1