Problem Description

You have a collection of apples and a basket that can hold a maximum weight of 5000 units.

You're given an integer array weight where weight[i] represents the weight of the i-th apple. Your task is to determine the maximum number of apples you can put in the basket without exceeding its weight capacity.

For example, if you have apples with weights [100, 200, 150, 1000] and your basket can carry up to 5000 units, you can put all 4 apples in the basket since their total weight is 1450, which is less than 5000.

The key insight is that to maximize the number of apples, you should prioritize lighter apples first. The solution sorts the apples by weight in ascending order and keeps adding them to the basket until adding another apple would exceed the 5000 unit limit. At that point, it returns the count of apples successfully added. If all apples fit within the weight limit, it returns the total number of apples.

Intuition

When faced with a constraint on total weight and the goal of maximizing count, a natural strategy emerges: prioritize the lightest items first. This is a classic greedy approach.

Think of it like packing for a trip with a weight limit on your luggage. If you want to bring as many items as possible, you'd pack your lightest items first - socks before shoes, t-shirts before jackets. The same principle applies here with apples.

By sorting the apples from lightest to heaviest, we ensure that we're always making the locally optimal choice at each step. Each time we add an apple to the basket, we're adding the lightest available apple, which leaves us with the maximum possible remaining capacity for future apples.

The beauty of this approach is that the local optimal choices lead to a global optimum. Why? Because if we were to swap any included light apple with an excluded heavier apple, we'd either exceed the weight limit or reduce the total count of apples we can carry.

The implementation becomes straightforward: sort the array, then iterate through it while keeping a running sum of weights. As soon as adding the next apple would exceed 5000 units, we stop and return the count. If we can add all apples without exceeding the limit, we return the total count.

This greedy strategy works because there's no benefit to choosing heavier apples over lighter ones when our only goal is to maximize quantity, not value or any other property.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a straightforward greedy algorithm that consists of two main steps:

Step 1: Sort the weights

weight.sort()

We sort the weight array in ascending order. This ensures we process apples from lightest to heaviest. Python's built-in sort() method uses Timsort, which has a time complexity of O(n log n).

Step 2: Accumulate weights until limit is exceeded

s = 0
for i, x in enumerate(weight):
    s += x
    if s > 5000:
        return i
return len(weight)

We iterate through the sorted array while maintaining a running sum s of the weights added so far. The enumerate() function gives us both the index i and the weight value x for each apple.

For each apple:

• Add its weight to the running sum s
• Check if the total weight exceeds 5000
• If it does, return the current index i, which represents the number of apples we successfully added before this one
• If we complete the loop without exceeding the limit, return len(weight), meaning all apples fit in the basket

Time Complexity: O(n log n) where n is the number of apples, dominated by the sorting operation.

Space Complexity: O(1) if we consider the sort operation to be in-place (though technically Python's sort uses O(n) auxiliary space in the worst case).

The algorithm guarantees the maximum number of apples because by always choosing the lightest available apple, we minimize the weight added at each step, leaving maximum capacity for additional apples.

Example Walkthrough

Let's walk through a concrete example with apples having weights [900, 950, 800, 1000, 700, 1800] and our basket capacity of 5000 units.

Step 1: Sort the weights in ascending order After sorting: [700, 800, 900, 950, 1000, 1800]

Step 2: Iterate through sorted weights, accumulating the sum

• Iteration 0:

  • Current apple weight: 700
  • Running sum: 0 + 700 = 700
  • Is 700 > 5000? No, continue

• Iteration 1:

  • Current apple weight: 800
  • Running sum: 700 + 800 = 1500
  • Is 1500 > 5000? No, continue

• Iteration 2:

  • Current apple weight: 900
  • Running sum: 1500 + 900 = 2400
  • Is 2400 > 5000? No, continue

• Iteration 3:

  • Current apple weight: 950
  • Running sum: 2400 + 950 = 3350
  • Is 3350 > 5000? No, continue

• Iteration 4:

  • Current apple weight: 1000
  • Running sum: 3350 + 1000 = 4350
  • Is 4350 > 5000? No, continue

• Iteration 5:

  • Current apple weight: 1800
  • Running sum: 4350 + 1800 = 6150
  • Is 6150 > 5000? Yes! Return index 5

Result: We can fit 5 apples in the basket (all except the heaviest one weighing 1800 units).

By choosing the lightest apples first [700, 800, 900, 950, 1000], we maximized our count. If we had greedily picked the heavier apples first, we would have gotten fewer apples. For instance, picking [1800, 1000, 950, 900] gives us only 4 apples with a total weight of 4650, even though we had room for more weight.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the number of apples. This is dominated by the sorting operation weight.sort(), which uses Python's Timsort algorithm with O(n × log n) time complexity in the average and worst cases. The subsequent iteration through the sorted array takes O(n) time, but this is absorbed by the higher complexity of sorting.

The space complexity is O(log n). While the sorting is performed in-place (modifying the original array without creating a new one), Python's Timsort algorithm requires O(log n) space for its internal recursion stack and temporary storage during the merge operations. The additional variables s and i only require O(1) space, so the overall space complexity is determined by the sorting algorithm's requirements.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Running Sum

While Python handles arbitrary precision integers automatically, in other languages like Java or C++, accumulating weights could cause integer overflow if the sum exceeds the maximum integer value before checking against 5000.

Solution: Use appropriate data types (like long in Java) or check for overflow before addition:

# Safe addition check (conceptual for languages with overflow)
if cumulative_weight > 5000 - apple_weight:
    return index
cumulative_weight += apple_weight

2. Modifying the Original Input Array

The sort() method modifies the input array in-place, which might be unexpected behavior if the caller needs to preserve the original order of weights.

Solution: Create a copy of the array before sorting:

def maxNumberOfApples(self, weight: List[int]) -> int:
    sorted_weight = sorted(weight)  # Creates a new sorted list
    # ... rest of the implementation

3. Off-by-One Error in Return Value

A common mistake is returning i + 1 when the weight limit is exceeded, thinking we need to count the apples included. However, since enumerate starts from 0 and we return before adding the current apple, i already represents the correct count.

Incorrect:

if cumulative_weight > 5000:
    return i + 1  # Wrong! This counts the apple that exceeded the limit

Correct:

if cumulative_weight > 5000:
    return i  # Correct - returns count of apples before exceeding limit

4. Edge Case: Empty Array

If the input array is empty, the current solution correctly returns 0, but it's worth explicitly handling this case for clarity:

Solution:

if not weight:
    return 0

5. Assuming All Weights are Positive

The solution assumes all apple weights are positive. If negative or zero weights are possible, the greedy approach might not work correctly as negative weights would be selected first after sorting.

Solution: Add validation or filter out non-positive weights:

weight = [w for w in weight if w > 0]
weight.sort()