easy Apple Redistribution into Boxes

Problem Statement

You are given an array apple of size n, where the apple[i] represents the number of apples in i^th pack. You are also given an array capacity of size m, where capacity[j] is a number of apples that can be stored in the j^th box.

Return the minimum number of boxes you need to use to put these all n packs of apples into boxes.

Note: You are allowed to distribute apples from the same pack into different boxes.

Examples

Example 1:

Input: apple = [2, 3, 1], capacity = [4, 2, 5, 1]
Expected Output: 2
Explanation: Box 1 can take apples from packs 1 and 2 partially (totaling 5 apples), and Box 2 can take the rest of 2 apples.

Example 2:

Input: apple = [4, 5, 6], capacity = [5, 10]
Expected Output: 2
Explanation: Box 1 can take apples from packs 1 and 2 partially (totaling 5 apples), and Box 2 can take the rest of pack 2 and all of pack 3 apples.

Example 3:

Input: apple = [1, 2, 5, 6], capacity = [2, 3, 7, 4, 5, 2, 4]
Expected Output: 3
Explanation: We can use boxes of size 7, 5, and 2 to pack all apples in boxes.

Constraints:

1 <= n == apple.length <= 50
1 <= m == capacity.length <= 50
1 <= apple[i], capacity[i] <= 50
The input is generated such that it's possible to redistribute packs of apples into boxes.

Try it yourself

Try solving this question here:

✅ Solution Apple Redistribution into Boxes

Problem Statement

Return the minimum number of boxes you need to use to put these all n packs of apples into boxes.

Note: You are allowed to distribute apples from the same pack into different boxes.

Examples

Example 1:

Input: apple = [2, 3, 1], capacity = [4, 2, 5, 1]
Expected Output: 2
Explanation: Box 1 can take apples from packs 1 and 2 partially (totaling 5 apples), and Box 2 can take the rest of 2 apples.

Example 2:

Input: apple = [4, 5, 6], capacity = [5, 10]
Expected Output: 2
Explanation: Box 1 can take apples from packs 1 and 2 partially (totaling 5 apples), and Box 2 can take the rest of pack 2 and all of pack 3 apples.

Example 3:

Input: apple = [1, 2, 5, 6], capacity = [2, 3, 7, 4, 5, 2, 4]
Expected Output: 3
Explanation: We can use boxes of size 7, 5, and 2 to pack all apples in boxes.

Constraints:

1 <= n == apple.length <= 50
1 <= m == capacity.length <= 50
1 <= apple[i], capacity[i] <= 50
The input is generated such that it's possible to redistribute packs of apples into boxes.

Solution

To solve this problem, we use sorting approach. The core idea is to efficiently distribute apples into boxes by always attempting to fill the largest capacity box available. This approach is believed to be effective because filling the largest boxes first reduces the number of boxes needed faster, akin to fitting the largest pieces into a puzzle first.

We will start by sorting the capacity array in descending order so we can always access the largest box first. The apples from each pack will be allocated starting from the box with the highest capacity, using a priority queue to manage and update the available space in the boxes quickly.

Step-by-step Algorithm

Step 1: Sort the boxCapacities array in ascending order to strategically use the largest boxes last.
Step 2: Initialize a variable totalApples to accumulate the total number of apples that need to be boxed.
Step 3: Iterate over the apples array to calculate totalApples by adding up all the apples in the packs.
Step 4: Initialize an index i to the last position of the boxCapacities array to start using boxes from the largest to the smallest.
Step 5: Use a while loop to distribute apples into boxes:
- Step 5a: Subtract the capacity of the box at index i from totalApples.
- Step 5b: Decrement the index i to move to the next largest box.
- Step 5c: Continue this process until all apples are distributed (totalApples <= 0) or there are no more boxes (i < 0).
Step 6: Calculate the number of boxes used, which is the difference between the total number of boxes and the boxes that were not used.

Algorithm Walkthrough

Let's consider the input: apple = [1, 2, 5, 6], capacity = [2, 3, 7, 4, 5, 2, 4]

Step 1: Original boxCapacities = [2, 3, 7, 4, 5, 2, 4]. Sorted boxCapacities = [2, 2, 3, 4, 4, 5, 7]
Step 2: Initialize totalApples = 0.
Step 3: Process apples:
- Adding apples from pack 1: totalApples = 1
- Adding apples from pack 2: totalApples = 3
- Adding apples from pack 3: totalApples = 8
- Adding apples from pack 4: totalApples = 14
Step 4: Initialize index i = 6 (last index of boxCapacities).
Step 5: Begin distributing apples:
- Step 5a: Using box with capacity 7: totalApples = 14 - 7 = 7
- Step 5b: Decrement i = 5
- Step 5a: Using box with capacity 5: totalApples = 7 - 5 = 2
- Step 5b: Decrement i = 4
- Step 5a: Using box with capacity 4: totalApples = 2 - 4 = -2 (all apples distributed, and extra capacity remains)
Step 6: Calculate boxes used:
- Initially, i = 6
- Final i = 4
- Boxes used = 6 - 4 + 1 = 3

Code

java


  // Method to determine the minimum number of boxes required to store all apples
  public int distributeApples(int[] apples, int[] boxCapacities) {
    // Sort the box capacities in ascending order to use the largest boxes last
    Arrays.sort(boxCapacities);
    int totalApples = 0;

    // Calculate the total number of apples
    for (int count : apples) {
      totalApples += count;
    }

    // Start from the largest box and subtract its capacity from the total apples until all apples are accounted for
    int i = boxCapacities.length - 1;
    while (i >= 0 && totalApples > 0) {
      totalApples -= boxCapacities[i];
      i--;
    }

    // The number of boxes used is the difference between the total number of boxes and the remaining boxes
    return boxCapacities.length - i - 1;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1
    int[] apples1 = { 2, 3, 1 };
    int[] capacities1 = { 4, 2, 5, 1 };
    System.out.println(
      "Example 1: Expected output is 1, Actual output is " +
        sol.distributeApples(apples1, capacities1)
    );

    // Example 2
    int[] apples2 = { 4, 5, 6 };
    int[] capacities2 = { 5, 10 };
    System.out.println(
      "Example 2: Expected output is 2, Actual output is " +
        sol.distributeApples(apples2, capacities2)
    );

    // Example 3
    int[] apples3 = { 1, 2, 5, 6 };
    int[] capacities3 = { 2, 3, 7, 4, 5, 2, 4 };
    System.out.println(
      "Example 3: Expected output is 3, Actual output is " +
        sol.distributeApples(apples3, capacities3)
    );
  }
}

Complexity Analysis

Time Complexity

Sorting the array (Arrays.sort(boxCapacities)): The time complexity of sorting an array is , where (m) is the number of boxes (length of the boxCapacities array).
Calculating the total number of apples: Iterating over the apples array takes time, where (n) is the number of apple packs.
Distributing apples into boxes: The while loop in the worst case will run for (m) iterations (if each box is used). This is .

Given that sorting the boxes dominates the complexity, the overall time complexity of the algorithm is .

Space Complexity

The space complexity used is for sorting.

🤖 Don't fully get this? Learn it with Claude

Stuck on Apple Redistribution into Boxes? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Apple Redistribution into Boxes** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Apple Redistribution into Boxes** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Apple Redistribution into Boxes**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Apple Redistribution into Boxes**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Advanced Sorting Techniques Sort Array by Increasing Frequency →