Problem

You have some apples and a basket that can carry up to 5000 units of weight.

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

Examples

Example 1:

1
2
3

Input: weight = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

Example 2:

1
2
3

Input: weight = [900,950,800,1000,700,800]
Output: 5
Explanation: The sum of weights of the 6 apples exceeds 5000 so we choose any 5 of them.

Constraints:

  • 1 <= weight.length <= 10^3
  • 1 <= weight[i] <= 10^3

Solution

Method 1 – Greedy + Sorting

Intuition

To maximize the number of apples in the basket without exceeding the weight limit, always pick the lightest apples first. This way, you can fit as many as possible before reaching the 5000 weight cap.

Approach

  1. Sort the array of apple weights in ascending order.
  2. Initialize a sum variable for the total weight and a counter for the number of apples.
  3. Iterate through the sorted weights:
    • Add the current apple’s weight to the sum.
    • If the sum exceeds 5000, stop and return the count.
    • Otherwise, increment the count.
  4. Return the count after the loop.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int maxNumberOfApples(vector<int>& weight) {
        sort(weight.begin(), weight.end());
        int sum = 0, ans = 0;
        for (int w : weight) {
            sum += w;
            if (sum > 5000) break;
            ++ans;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func maxNumberOfApples(weight []int) int {
    sort.Ints(weight)
    sum, ans := 0, 0
    for _, w := range weight {
        sum += w
        if sum > 5000 {
            break
        }
        ans++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int maxNumberOfApples(int[] weight) {
        Arrays.sort(weight);
        int sum = 0, ans = 0;
        for (int w : weight) {
            sum += w;
            if (sum > 5000) break;
            ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun maxNumberOfApples(weight: IntArray): Int {
        weight.sort()
        var sum = 0
        var ans = 0
        for (w in weight) {
            sum += w
            if (sum > 5000) break
            ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxNumberOfApples(self, weight: list[int]) -> int:
        weight.sort()
        s = 0
        ans = 0
        for w in weight:
            s += w
            if s > 5000:
                break
            ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn max_number_of_apples(weight: Vec<i32>) -> i32 {
        let mut w = weight;
        w.sort();
        let mut s = 0;
        let mut ans = 0;
        for x in w {
            s += x;
            if s > 5000 { break; }
            ans += 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maxNumberOfApples(weight: number[]): number {
        weight.sort((a, b) => a - b);
        let s = 0, ans = 0;
        for (const w of weight) {
            s += w;
            if (s > 5000) break;
            ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the weights, where n is the number of apples.
  • 🧺 Space complexity: O(1), if sorting in-place, otherwise O(n) for a copy.