How Many Apples Can You Put into the Basket

easy greedy sorting array

Problem

You have a basket that can carry apples with total weight not exceeding 5000 units. Given an array weight where weight[i] is the weight of the i-th apple, return the maximum number of apples you can put in the basket.

Inputweight = [100, 200, 150, 1000]

Output4

All 4 apples sum to 1450 ≤ 5000, so every apple fits.

weight (comma-separated)

capacity

def max_number_of_apples(weight):
    weight.sort()
    total = 0
    count = 0
    for w in weight:
        if total + w > 5000:
            break
        total += w
        count += 1
    return count

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

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

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

Explanation

We want to fit the most apples, not the heaviest ones, into a basket with a weight limit. The smart move is simple: take the lightest apples first. Every light apple you add leaves more room for even more apples.

So we sort the weights from smallest to largest and then keep adding apples while there is still room. We track a running total weight and a count of how many apples we've packed.

For each apple w, we check if adding it keeps us under the limit (total + w > 5000 would overflow). The moment one apple doesn't fit, every remaining apple is at least as heavy, so none of them fit either — we stop immediately and return count.

This greedy choice is optimal because picking the lightest apples maximizes how many you can include before the cap is hit.

Example: weight = [100, 200, 150, 1000] sorts to [100, 150, 200, 1000]. Running total: 100, 250, 450, 1450 — all stay under 5000, so all 4 apples fit and the answer is 4.

Time: O(n log n) Space: O(1)