Problem Description

You are given an array weight where each element represents the weight of an apple. You also have a basket that can carry at most 5000 units of weight. Your task is to determine the maximum number of apples you can put into the basket without exceeding the weight limit.

Key constraints:

• Each apple can be used at most once (no reuse).
• The sum of the weights of the chosen apples must not exceed 5000.
• There is always at least one valid solution (possibly picking no apples).

Thought Process

At first glance, it might seem like we need to try all possible combinations of apples to find the largest group that fits within the weight limit—this would be an exhaustive, brute-force approach. However, since we want to maximize the number of apples (not the total weight), we should focus on picking as many light apples as possible.

The lighter the apple, the less it contributes to the total weight, allowing us to include more apples overall. This suggests that sorting the apples by weight and picking them in increasing order is likely the best strategy. This is a classic greedy approach, where we always make the optimal local choice (the lightest apple next) to build up to the global optimum.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Sort the weights: Arrange the weight array in ascending order so that we can always consider the lightest apple first.
2. Iterate and accumulate: Initialize a running sum (curr_weight) and a counter (count). Iterate through the sorted list, and for each apple:
   • If adding its weight keeps the total at or below 5000, include it (increment count and update curr_weight).
   • If adding it would exceed 5000, stop—the basket can't hold any more apples.
3. Return the count: After the loop, count holds the maximum number of apples that fit.

We use sorting because it allows us to always pick the smallest available apple, and iterating through the sorted array ensures we never miss a better combination (since heavier apples would always use up more capacity per apple).

Example Walkthrough

Let's use the input weight = [100, 200, 150, 1000]:

1. Sort the weights: [100, 150, 200, 1000]
2. Start with curr_weight = 0, count = 0.
   • Add 100: curr_weight = 100, count = 1
   • Add 150: curr_weight = 250, count = 2
   • Add 200: curr_weight = 450, count = 3
   • Add 1000: curr_weight = 1450, count = 4
3. All apples fit, so the answer is 4.

If the next apple in the list had made curr_weight exceed 5000, we would have stopped before adding it.

Code Implementation

class Solution:
    def maxNumberOfApples(self, weight):
        weight.sort()
        curr_weight = 0
        count = 0
        for w in weight:
            if curr_weight + w > 5000:
                break
            curr_weight += w
            count += 1
        return count
      

class Solution {
public:
    int maxNumberOfApples(vector<int>& weight) {
        sort(weight.begin(), weight.end());
        int curr_weight = 0, count = 0;
        for (int w : weight) {
            if (curr_weight + w > 5000) break;
            curr_weight += w;
            count++;
        }
        return count;
    }
};
      

class Solution {
    public int maxNumberOfApples(int[] weight) {
        Arrays.sort(weight);
        int curr_weight = 0, count = 0;
        for (int w : weight) {
            if (curr_weight + w > 5000) break;
            curr_weight += w;
            count++;
        }
        return count;
    }
}
      

var maxNumberOfApples = function(weight) {
    weight.sort((a, b) => a - b);
    let curr_weight = 0, count = 0;
    for (let w of weight) {
        if (curr_weight + w > 5000) break;
        curr_weight += w;
        count++;
    }
    return count;
};
      

Time and Space Complexity

Brute-force approach: If we tried every combination of apples, the time complexity would be exponential, specifically O(2ⁿ), as there are 2ⁿ possible subsets. This is infeasible for large inputs.

Optimized (Greedy) approach:

• Time Complexity: Sorting the array takes O(n log n). Iterating through the apples is O(n). Thus, the total time complexity is O(n log n).
• Space Complexity: Sorting may require O(n) extra space (depending on the language and implementation), but otherwise, we only use a few variables: O(1) additional space.

Summary

The problem asks us to maximize the number of apples in a basket without exceeding a weight limit. The key insight is that, to fit as many apples as possible, we should always pick the lightest apples first. This leads to a greedy algorithm: sort the weights, then add apples in order until the basket can't hold any more. This approach is simple, efficient, and leverages the problem's structure for an elegant solution.