Apple Redistribution into Boxes solution and explanation
Google
9 more videos on this problem
Apple Redistribution into Boxes | Simple Explanation | Homework Inside | Leetcode 3074 | MIKcodestorywithMIK · 9:53 · 3K views
Leetcode | 3074. Apple Redistribution into Boxes | Easy | Java SolutionDeveloper Docs · 5:13 · 772 views
Apple Redistribution into Boxes | LeetCode 3074 | Beginner FriendlySanyam IIT Guwahati · 7:35 · 315 views
3074. Apple Redistribution into Boxes | Leetcode Daily - PythonLeetcode Daily · 9:06 · 313 views
3074. Apple Redistribution into Boxes (Leetcode Easy)Programming Live with Larry · 3:47 · 228 views
Apple Redistribution into Boxes 🔥 | LeetCode 3074 | Greedy + Sorting | Optimal Solution Study Placement · 4:55 · 164 views
Apple Redistribution into Boxes | LeetCode 3074 | Java Code | Developer CoderDeveloper Coder · 6:59 · 111 views
3074. Apple Redistribution into Boxes #leetcodequestionandanswers #java #coding #array #greedyCodeVia · 3:19 · 110 views
LeetCode Daily 3074 | Apple Redistribution into Boxes (Sorting + Greedy) | Easy | SolutionDaily Dose Of LeetCode · 8:04 · 71 views
3074. Apple Redistribution into Boxes || LeetCode Weekly Contest 388Coding Club RVCE · 4:19 · 51 views
The problem
You are given an array apple of size n and an array capacity of size m.
There are n packs where the ith pack contains apple[i] apples. There are m boxes as well, and the ith box has a capacity of capacity[i] apples.
Return the minimum number of boxes you need to select to redistribute these n packs of apples into boxes.
Note that, apples from the same pack can be distributed into different boxes.
Example 1:
Input: apple = [1,3,2], capacity = [4,3,1,5,2] Output: 2 Explanation: We will use boxes with capacities 4 and 5. It is possible to distribute the apples as the total capacity is greater than or equal to the total number of apples.
Example 2:
Input: apple = [5,5,5], capacity = [2,4,2,7] Output: 4 Explanation: We will need to use all the boxes.
Constraints:
1 <= n == apple.length <= 501 <= m == capacity.length <= 501 <= apple[i], capacity[i] <= 50- The input is generated such that it's possible to redistribute packs of apples into boxes.
Approach overview
Problem Overview: You are given two arrays: apple representing apples in each pack and capacity representing the capacity of available boxes. The goal is to redistribute all apples into the minimum number of boxes without exceeding any box’s capacity.
Approach 1: Greedy with Sorting (O(n log n) time, O(1) extra space)
This problem reduces to a simple observation: the total number of apples matters, not which pack they came from. First compute the total apples using a single pass through the apple array. Then sort the capacity array in descending order and keep picking the largest box capacities until their combined capacity can hold all apples. The greedy choice works because using the largest boxes first minimizes the number of boxes required. Sorting dominates the runtime at O(m log m) where m is the number of boxes, while the accumulation step is linear.
The approach relies on concepts commonly used in Greedy strategies: always take the locally optimal choice (largest capacity) to reach a global optimum. Sorting the capacities is what makes the greedy selection straightforward, connecting the solution to patterns from Sorting problems.
Approach 2: Priority Queue (Heap) Selection (O(m log m) time, O(m) space)
Instead of sorting all capacities upfront, push every box capacity into a priority queue and repeatedly extract the largest capacity box until the total capacity covers all apples. Each extraction represents selecting the next best box. If a max‑heap is not directly available, you can simulate it by inserting negative values into a min‑heap. Every heap insertion and removal costs O(log m), resulting in O(m log m) overall time.
This method is useful when capacities arrive dynamically or when you only need the top few elements rather than a fully sorted array. The data structure involved is a Priority Queue, which efficiently retrieves the largest remaining capacity each step.
Recommended for interviews: The greedy sorting approach is what most interviewers expect. It shows you recognize that the order of apple packs is irrelevant and that minimizing boxes simply means selecting the largest capacities first. The heap version demonstrates familiarity with priority queues but is usually unnecessary since sorting is simpler and slightly more memory efficient. Showing the greedy reasoning clearly is the key signal of strong problem‑solving skills.
Approach 1: Greedy Approach for Minimizing Box Usage
This approach suggests sorting the box capacities in descending order and continuously filling the boxes until all apple packs are distributed. The greedy nature ensures we utilize boxes with maximum capacity first, minimizing the total number of boxes used.
def min_boxes(apple, capacity):
total_apples = sum(apple)
capacity.sort(reverse=True)
boxes_used = 0
for c in capacity:
total_apples -= c
boxes_used += 1
if total_apples <= 0:
return boxes_used
return boxes_used
apple = [1, 3, 2]
capacity = [4, 3, 1, 5, 2]
print("Minimum number of boxes:", min_boxes(apple, capacity))import java.util.Arrays;
public class AppleDistribution {
public static int minBoxes(int[] apple, int[] capacity) {
int totalApples = 0;
for (int a : apple) totalApples += a;
Arrays.sort(capacity);
int boxesUsed = 0;
for (int i = capacity.length - 1; i >= 0; i--) {
totalApples -= capacity[i];
boxesUsed++;
if (totalApples <= 0) return boxesUsed;
}
return boxesUsed;
}
public static void main(String[] args) {
int[] apple = {1, 3, 2};
int[] capacity = {4, 3, 1, 5, 2};
System.out.println("Minimum number of boxes: " + minBoxes(apple, capacity));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minBoxes(std::vector<int>& apple, std::vector<int>& capacity) {
int totalApples = 0;
for (int a : apple) totalApples += a;
std::sort(capacity.rbegin(), capacity.rend());
int boxesUsed = 0;
for (int c : capacity) {
if (totalApples <= 0) break;
totalApples -= c;
boxesUsed++;
}
return boxesUsed;
}
int main() {
std::vector<int> apple = {1, 3, 2};
std::vector<int> capacity = {4, 3, 1, 5, 2};
std::cout << "Minimum number of boxes: " << minBoxes(apple, capacity) << std::endl;
return 0;
}function minBoxes(apple, capacity) {
let totalApples = apple.reduce((acc, val) => acc + val, 0);
capacity.sort((a, b) => b - a);
let boxesUsed = 0;
for (let c of capacity) {
totalApples -= c;
boxesUsed++;
if (totalApples <= 0) {
return boxesUsed;
}
}
return boxesUsed;
}
const apple = [1, 3, 2];
const capacity = [4, 3, 1, 5, 2];
console.log("Minimum number of boxes:", minBoxes(apple, capacity));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)b - *(int *)a);
}
int minBoxes(int* apple, int n, int* capacity, int m) {
int totalApples = 0;
for (int i = 0; i < n; i++) totalApples += apple[i];
qsort(capacity, m, sizeof(int), compare);
int boxesUsed = 0;
for (int i = 0; i < m; i++) {
totalApples -= capacity[i];
boxesUsed++;
if (totalApples <= 0) return boxesUsed;
}
return boxesUsed;
}
int main() {
int apple[] = {1, 3, 2};
int capacity[] = {4, 3, 1, 5, 2};
int n = 3;
int m = 5;
printf("Minimum number of boxes: %d\n", minBoxes(apple, n, capacity, m));
return 0;
}using System;
using System.Linq;
class AppleDistribution {
public static int MinBoxes(int[] apple, int[] capacity) {
int totalApples = apple.Sum();
Array.Sort(capacity);
Array.Reverse(capacity);
int boxesUsed = 0;
foreach (int c in capacity) {
totalApples -= c;
boxesUsed++;
if (totalApples <= 0) return boxesUsed;
}
return boxesUsed;
}
static void Main() {
int[] apple = {1, 3, 2};
int[] capacity = {4, 3, 1, 5, 2};
Console.WriteLine("Minimum number of boxes: " + MinBoxes(apple, capacity));
}
}The Python solution uses a straightforward approach, where the capacity list is sorted in descending order. Then, using a for loop, it decrements the total apples by the box capacities, one by one, until all apples are distributed.
Time Complexity: O(m log m) due to sorting, followed by a linear scan making it O(m log m).
Space Complexity: O(1) with list sorting done in place.
Approach 2: Use of Priority Queue (Min-Heap Structure)
This approach is alternative to the greedy method, which leverages a priority queue (min-heap) to manage capacities and ensures that the smallest required boxes are filled first. This can be useful in scenarios where random access to the smallest element is necessary. Although it may not be optimal for the current arrangement, it provides a perspective on alternative sorting.
import heapq
def min_boxes(apple, capacity):
total_apples = sum(apple)
heapq.heapify(capacity)
boxes_used = 0
while total_apples > 0:
total_apples -= heapq.heappop(capacity)
boxes_used += 1
return boxes_used
apple = [1, 3, 2]
capacity = [4, 3, 1, 5, 2]
print("Minimum number of boxes:", min_boxes(apple, capacity))#include <iostream>
#include <vector>
#include <queue>
int minBoxes(std::vector<int>& apple, std::vector<int>& capacity) {
int totalApples = 0;
for (int a : apple) totalApples += a;
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int c : capacity) minHeap.push(-c);
int boxesUsed = 0;
while (totalApples > 0) {
totalApples += minHeap.top();
minHeap.pop();
boxesUsed++;
}
return boxesUsed;
}
int main() {
std::vector<int> apple = {1, 3, 2};
std::vector<int> capacity = {4, 3, 1, 5, 2};
std::cout << "Minimum number of boxes: " << minBoxes(apple, capacity) << std::endl;
return 0;
}The Python implementation takes advantage of the `heapq` library to create a min-heap of box capacities, using the heap to find the smallest element to use for reducing the apple count efficiently.
Time Complexity: O(m log m), relating to heap operations.
Space Complexity: O(m) due to priority queue nature.
Approach 3: Greedy + Sorting
To minimize the number of boxes needed, we should prioritize using boxes with larger capacities. Therefore, we can sort the boxes in descending order of capacity, and then use the boxes one by one until all the apples are packed. We return the number of boxes used at this point.
The time complexity is O(m times log m + n) and the space complexity is O(log m), where m and n are the lengths of the arrays capacity and apple respectively.
function minimumBoxes(apple: number[], capacity: number[]): number {
capacity.sort((a, b) => b - a);
let s = apple.reduce((acc, cur) => acc + cur, 0);
for (let i = 1; ; ++i) {
s -= capacity[i - 1];
if (s <= 0) {
return i;
}
}
}func minimumBoxes(apple []int, capacity []int) int {
sort.Ints(capacity)
s := 0
for _, x := range apple {
s += x
}
for i := 1; ; i++ {
s -= capacity[len(capacity)-i]
if s <= 0 {
return i
}
}
}impl Solution {
pub fn minimum_boxes(apple: Vec<i32>, mut capacity: Vec<i32>) -> i32 {
capacity.sort();
let mut s: i32 = apple.iter().sum();
let n = capacity.len();
let mut i = 1;
loop {
s -= capacity[n - i];
if s <= 0 {
return i as i32;
}
i += 1;
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach for Minimizing Box Usage | Time Complexity: O(m log m) due to sorting, followed by a linear scan making it O(m log m). |
| Use of Priority Queue (Min-Heap Structure) | Time Complexity: O(m log m), relating to heap operations. |
| Greedy + Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(m log m) | O(1) | Best general solution. Simple implementation and minimal memory usage. |
| Priority Queue (Heap) | O(m log m) | O(m) | Useful when capacities arrive dynamically or when repeatedly selecting the largest element. |
Frequently asked questions
Is Apple Redistribution into Boxes easy or hard?
Apple Redistribution into Boxes is classified as an Easy problem on LeetCode with a high acceptance rate around 78%. The challenge mainly tests whether you recognize the greedy insight that selecting the largest box capacities first minimizes the number of boxes required.
Apple Redistribution into Boxes Python/Java solution
Most implementations follow the same steps: sum all apples, sort the capacity array in descending order, and accumulate capacities until the total meets or exceeds the apple count. This logic translates directly into Python, Java, C++, JavaScript, and other languages with built-in sorting utilities.
How to solve Apple Redistribution into Boxes in O(n)?
A true O(n) solution generally requires constraints such as bounded capacities that allow counting sort or bucket techniques. In the general case with arbitrary values, the optimal practical solution sorts the capacities and runs in O(m log m) time. The greedy selection of the largest capacities ensures the minimum number of boxes.
What is the best approach for Apple Redistribution into Boxes?
The most efficient approach is a greedy strategy. First calculate the total number of apples, then sort the box capacities in descending order and keep selecting the largest boxes until their combined capacity holds all apples. Sorting costs O(m log m) time where m is the number of boxes, and the rest of the process is linear.
Is Apple Redistribution into Boxes asked at Google/Amazon/Meta?
Problems using greedy selection and capacity allocation patterns frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary in wording, the underlying technique of sorting resources and selecting the largest first is a common interview pattern.
What data structure is used in Apple Redistribution into Boxes?
The primary data structure is an array combined with sorting for the greedy solution. An alternative implementation uses a priority queue (max-heap) to repeatedly extract the box with the largest remaining capacity.
What is the time complexity of Apple Redistribution into Boxes?
The optimal solution runs in O(m log m) time due to sorting the box capacities. After sorting, you accumulate capacities until they cover the total number of apples, which takes O(m) time. Space complexity is O(1) if sorting is done in place.