LeetCode 1196 - How Many Apples Can You Put into the Basket

This problem is asking us to determine how many apples we can fit into a basket with a maximum carrying capacity of 5000 units of weight. We are given an array weight where each element represents the weight of a single apple.

leetcodeeasyarraygreedysorting

LeetCode Problem 1196

Difficulty: 🟢 Easy
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

This problem is asking us to determine how many apples we can fit into a basket with a maximum carrying capacity of 5000 units of weight. We are given an array weight where each element represents the weight of a single apple. The goal is to maximize the number of apples placed into the basket without exceeding its weight limit.

In other words, we want to count the largest subset of apples such that the sum of their weights does not exceed 5000. The output is a single integer representing this maximum count.

The constraints provide important information: the number of apples can be up to 103, and each apple's weight can be up to 103. This tells us that we are dealing with small input sizes, so algorithms with a time complexity up to O(n log n) or O(n²) are acceptable. The problem guarantees all weights are positive integers, and there will be at least one apple, so we do not need to handle empty arrays.

Important edge cases include having all apples very light, all apples very heavy, or a mix of weights that sum exactly to 5000. Another edge case is when a single apple exceeds the basket capacity.

Approaches

The brute-force approach is to consider every subset of apples, compute their total weight, and track the maximum number of apples that fit without exceeding 5000. This guarantees correctness because it examines every combination, but it is impractical because there are 2^n possible subsets. For n = 103, this is astronomically large.

The key insight for a more efficient solution is greedy: lighter apples consume less capacity, so we can fit more apples by starting with the smallest weights. Sorting the array and iterating through it in increasing order allows us to count apples until adding the next apple would exceed the basket's capacity. This works because adding heavier apples first could prevent us from including more lighter apples later, while including lighter apples first maximizes the count.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Examine all subsets to find the maximum number of apples
Optimal (Greedy + Sorting) O(n log n) O(1) Sort weights and pick apples starting from the lightest until capacity is reached

Algorithm Walkthrough

  1. Sort the weight array in ascending order so that the lightest apples are considered first. This ensures we maximize the number of apples added without exceeding the basket's capacity.
  2. Initialize two variables: total_weight to track the cumulative weight in the basket and count to track the number of apples added.
  3. Iterate through the sorted weights. For each apple:
  • Check if adding the apple's weight to total_weight would exceed 5000.
  • If it would not, add the weight to total_weight and increment count.
  • If it would exceed the limit, stop iterating because any subsequent apples will be heavier and cannot fit either.
  1. Return count as the maximum number of apples that can fit in the basket.

Why it works: Sorting ensures we always pick the smallest available apple first. This guarantees that at every step, we are adding an apple only if it keeps the total weight within capacity. Once we cannot fit an apple, no further apple in the sorted order can fit, so stopping is correct.

Python Solution

from typing import List

class Solution:
    def maxNumberOfApples(self, weight: List[int]) -> int:
        weight.sort()
        total_weight = 0
        count = 0
        
        for w in weight:
            if total_weight + w > 5000:
                break
            total_weight += w
            count += 1
        
        return count

The implementation starts by sorting the list of weights. We maintain total_weight and count to track the basket status. For each apple, we check if it fits. If it does, we include it and update the running total and count. If it does not, we stop because no subsequent apples can fit. Finally, we return the total count.

Go Solution

import "sort"

func maxNumberOfApples(weight []int) int {
    sort.Ints(weight)
    totalWeight := 0
    count := 0
    
    for _, w := range weight {
        if totalWeight + w > 5000 {
            break
        }
        totalWeight += w
        count++
    }
    
    return count
}

The Go version follows the same logic as Python. We use sort.Ints to sort the slice, and variables totalWeight and count track the running weight and number of apples. The loop iterates over the sorted slice and breaks once adding an apple would exceed 5000. Go-specific considerations include using slices, which are nil-safe, and integer addition is safe here due to constraints.

Worked Examples

Example 1: weight = [100,200,150,1000]

  1. Sort: [100, 150, 200, 1000]
  2. total_weight = 0, count = 0
  3. Add 100: total_weight = 100, count = 1
  4. Add 150: total_weight = 250, count = 2
  5. Add 200: total_weight = 450, count = 3
  6. Add 1000: total_weight = 1450, count = 4
  7. No more apples. Return 4

Example 2: weight = [900,950,800,1000,700,800]

  1. Sort: [700, 800, 800, 900, 950, 1000]
  2. total_weight = 0, count = 0
  3. Add 700: total_weight = 700, count = 1
  4. Add 800: total_weight = 1500, count = 2
  5. Add 800: total_weight = 2300, count = 3
  6. Add 900: total_weight = 3200, count = 4
  7. Add 950: total_weight = 4150, count = 5
  8. Next apple 1000 would exceed 5000, stop. Return 5

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the complexity; iterating through the sorted list is O(n)
Space O(1) Sorting can be done in-place; no extra data structures used

The algorithm is efficient for n up to 103 due to the small input size. Sorting ensures the greedy selection maximizes the count without requiring combinatorial exploration.

Test Cases

# provided examples
assert Solution().maxNumberOfApples([100,200,150,1000]) == 4  # all fit
assert Solution().maxNumberOfApples([900,950,800,1000,700,800]) == 5  # sum exceeds 5000

# boundary tests
assert Solution().maxNumberOfApples([5000]) == 1  # exactly fits
assert Solution().maxNumberOfApples([5001]) == 0  # cannot fit single apple
assert Solution().maxNumberOfApples([1]*5000) == 5000  # many light apples

# mix of heavy and light
assert Solution().maxNumberOfApples([1000,2000,3000,4000,100]) == 2  # pick 100 + 1000

# minimal input
assert Solution().maxNumberOfApples([1]) == 1  # single apple fits
Test Why
[100,200,150,1000] Simple case where all apples fit
[900,950,800,1000,700,800] Sum exceeds 5000; ensures greedy selection works
[5000] Apple exactly matches capacity
[5001] Single apple exceeds capacity
[1]*5000 Stress test with many small apples
[1000,2000,3000,4000,100] Mix of heavy and light apples to test selection
[1] Minimal input case

Edge Cases

One edge case is when an individual apple exceeds the basket capacity, e.g., [6000]. Our implementation correctly returns 0 because the check total_weight + w > 5000 prevents adding it.

Another edge case is when all apples are extremely light, such as [1]*5000. Here, the greedy algorithm will iterate through all apples and correctly count all 5000 as fitting.

A third edge case is when the total weight is exactly 5000, e.g., [2000,1500,1500]. The algorithm will include apples sequentially until the total reaches 5000 and stop without exceeding it, returning the maximum possible count.

This covers the boundary, minimal, and maximal selection scenarios, ensuring correctness across typical and extreme inputs.