Apple Redistribution into Boxes — Problem & Solution
Apple Redistribution into Boxes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Apple Redistribution into Boxes is an easy coding problem on arrays, sorting and greedy, asked in Amazon, Google and Cognizant interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google, Cognizant
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
apple[i] apples are packed in the i-th pack, and capacity[j] is how many apples box j holds. A pack's apples may be split across boxes.
Return the minimum number of boxes needed to hold every apple. The input always allows a solution.
Example 1
Input: apple = [1,3,2], capacity = [4,3,1,5,2]
Output: 2
Explanation: Six apples fit in the boxes of size 5 and 4.
Example 2
Input: apple = [5,5,5], capacity = [2,4,2,7]
Output: 4
Explanation: Fifteen apples need every box.
Example 3
Input: apple = [1], capacity = [10]
Output: 1
Constraints
1 <= apple.length <= 501 <= capacity.length <= 501 <= apple[i], capacity[i] <= 50The input is generated so that it is possible to redistribute the apples.
Hints for Apple Redistribution into Boxes
Hint 1
Because packs can be split, only the total number of apples matters.
Hint 2
To use as few boxes as possible, fill the largest ones first.
Hint 3
Sort the capacities descending and take them until the total is covered.
How to solve Apple Redistribution into Boxes
Splitting packs means only the total count matters, so sort the capacities largest-first and take boxes until their combined capacity reaches the total.
Approach
- Sum the apples.
- Sort
capacitydescending. - Take boxes in that order, subtracting each capacity, until the remaining total is non-positive.
- Return how many boxes were taken.
Why it works
Splitting is what collapses this to a single number: without it, packs would have to be assigned whole and the problem would become bin packing. With it, any set of boxes whose capacities sum to at least the total works, so the greedy largest-first choice is optimal.
Complexity
- Time —
O(m log m) - Space —
O(m)
Pitfalls
- Sorting ascending uses more boxes than necessary.
- The individual pack sizes never matter, only the total.
- The loop must stop as soon as the total is covered.
Reference solution
Python
from typing import List
def minimumBoxes(apple: List[int], capacity: List[int]) -> int:
total = sum(apple)
used = 0
for c in sorted(capacity, reverse=True):
if total <= 0:
break
total -= c
used += 1
return usedJava
public static int minimumBoxes(int[] apple, int[] capacity) {
int total = 0;
for (int v : apple) total += v;
Integer[] sorted = new Integer[capacity.length];
for (int i = 0; i < capacity.length; i++) sorted[i] = capacity[i];
Arrays.sort(sorted, Comparator.reverseOrder());
int used = 0;
for (int c : sorted) {
if (total <= 0) break;
total -= c;
used++;
}
return used;
}C++
int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
int total = 0;
for (int v : apple) total += v;
vector<int> sorted = capacity;
sort(sorted.begin(), sorted.end(), greater<int>());
int used = 0;
for (int c : sorted) {
if (total <= 0) break;
total -= c;
used++;
}
return used;
}JavaScript
var minimumBoxes = function(apple, capacity) {
var total = 0, i;
for (i = 0; i < apple.length; i++) total += apple[i];
var sorted = capacity.slice();
sorted.sort(function(a, b) { return b - a; });
var used = 0;
for (i = 0; i < sorted.length; i++) {
if (total <= 0) break;
total -= sorted[i];
used++;
}
return used;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms