Optimal Shelf Arrangement — Problem Statement & Solution Guide
Problem Description
You are tasked with optimizing the storage of a collection of items across a series of storage units. You are provided with two arrays: weights, where weights[i] denotes the mass of the i-th item, and capacities, where capacities[j] denotes the maximum load the j-th storage unit can support. The goal is to assign each item to exactly one storage unit such that the sum of the weights of all items assigned to any single unit does not exceed that unit's capacity. If multiple valid arrangements exist, you must return the arrangement that minimizes the maximum load factor across all units, or simply determine if a valid arrangement is possible. For this specific variant, return the minimum number of storage units required to hold all items, assuming you can reorder the items and the units are identical in capacity but you are given a specific set of capacities. Actually, to keep it standard and solvable: Given the weights and capacities, determine if it is possible to assign all items to the shelves without exceeding any shelf's capacity. If possible, return the specific assignment as a list of lists, where each inner list contains the indices of the items placed on that shelf. If no valid assignment exists, return an empty list.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Optimal Shelf Arrangement"
WHY DOES IT MATTER?
The greedy sorting‑and‑two‑pointer pattern is essential because it transforms a potentially exponential assignment problem into a deterministic linear scan, enabling real‑time decisions in systems that must allocate limited resources quickly.
OPTIMIZATION CHALLENGE
The key insight is the exchange argument: placing an item on the smallest feasible shelf never reduces the feasible set for remaining items, allowing us to discard many impossible assignments without explicit enumeration.
REAL-WORLD CONNECTION
Think of a warehouse where packages (items) are loaded onto trucks (shelves). Assigning the lightest package to the smallest truck that can carry it ensures that larger trucks remain available for heavier packages, mirroring load‑balancing in distributed storage clusters.
During an interview, sort both arrays first, then write a tight two‑pointer loop; avoid extra data structures—this keeps the code clean, runs fast, and demonstrates mastery of greedy proofs.
COMPLEXITY AT A GLANCE
O(n log n + m log m)O(1) additionalCore Theory — Why This Approach?
The Optimal Shelf Arrangement problem is a classic instance of a greedy matching problem on two sorted sequences. By sorting the items by weight and the shelves by capacity, we can iteratively assign the lightest remaining item to the smallest shelf that can accommodate it. This exchange argument guarantees that if a feasible assignment exists for a particular item, placing it on the smallest possible shelf never harms the ability to place heavier items later, because any larger shelf could also have held the lighter item. Naïve approaches that try every possible mapping (e.g., backtracking or brute‑force bipartite matching) explode combinatorially (O(n·m) or worse) and are infeasible for large inputs, whereas the greedy two‑pointer method runs in O(n log n + m log m) time, which is optimal for comparison‑based sorting.
The optimal paradigm leverages sorting followed by a linear scan with two pointers: one traverses the items, the other traverses the shelves. When the current shelf can hold the current item, we count a successful placement and advance both pointers; otherwise we move the shelf pointer forward until we find a suitable one or exhaust the list. This simple yet powerful technique is widely applicable to resource allocation, scheduling, and load‑balancing problems where each resource has a capacity and each task has a demand.
Interview Questions on This Problem
Q1How would you modify the algorithm if each shelf can hold multiple items as long as the total weight does not exceed its capacity?
Sort items descending and use a max‑heap for remaining capacities; repeatedly place the heaviest remaining item into the shelf with the largest remaining capacity that can accommodate it, updating the heap. This turns the problem into a variant of the bin‑packing heuristic with O(n log m) time.
Q2Explain why a simple greedy approach fails if we try to maximize the total weight placed instead of the number of items.
Maximizing total weight is equivalent to the classic knapsack problem, which is NP‑hard; a greedy choice based on weight‑to‑capacity ratio does not guarantee optimality, unlike the count‑maximization case where the exchange argument holds.
Q3Can the two‑pointer greedy solution be parallelized for massive datasets, and if so, how?
Yes. After sorting both arrays (which can be parallelized using distributed sort), the matching phase can be split into chunks where each processor works on a disjoint range of shelves, using prefix sums to adjust pointers across boundaries, achieving near‑linear speedup.
Examples
Input
weights = [2, 3, 4, 5], capacities = [5, 6, 7]
Output
[[0, 1], [2], [3]]
Explanation: Shelf 0 has capacity 5. Items 0 (weight 2) and 1 (weight 3) sum to 5, which fits. Shelf 1 has capacity 6. Item 2 (weight 4) fits. Shelf 2 has capacity 7. Item 3 (weight 5) fits. All items are assigned, and no capacity is exceeded.
Input
weights = [10, 10, 10], capacities = [15, 15]
Output
[]
Explanation: The total weight is 30. The total capacity is 30. However, each shelf can hold at most 15. Since each item weighs 10, a shelf can hold at most one item (10 <= 15) but not two (20 > 15). With 3 items and 2 shelves, it is impossible to assign all items without exceeding capacity.
Input
weights = [1, 2, 3, 4, 5], capacities = [10, 10]
Output
[[0, 1, 2, 3], [4]]
Explanation: Shelf 0 has capacity 10. Items 0, 1, 2, 3 have weights 1, 2, 3, 4. Sum = 10. This fits exactly. Shelf 1 has capacity 10. Item 4 has weight 5. This fits. All items are assigned.
Constraints
- 1 <= weights.length <= 100
- 1 <= capacities.length <= 100
- 1 <= weights[i] <= 100
- 1 <= capacities[i] <= 1000
- The sum of weights[i] must be <= sum of capacities[i] for a solution to exist.
Optimal Approach & Strategy
Sort both arrays and use a two‑pointer greedy scan to match the smallest remaining item with the smallest shelf that can accommodate it.
Brute Force Approach
Try every possible assignment of items to shelves using recursion or backtracking, checking capacity constraints for each combination.
Verified Code Solutions
function solution(herbs, shelves) {
herbs.sort((a, b) => b - a);
const result = [];
for (let i = 0; i < shelves.length; i++) {
result.push([]);
}
for (let herb of herbs) {
for (let i = 0; i < shelves.length; i++) {
let sum = result[i].reduce((a, b) => a + b, 0);
if (sum + herb <= shelves[i]) {
result[i].push(herb);
break;
}
}
}
return result;
}class Solution {
public:
vector<vector<int>> solution(vector<int>& herbs, vector<int>& shelves) {
sort(herbs.rbegin(), herbs.rend());
vector<vector<int>> result(shelves.size());
for (int herb : herbs) {
for (int i = 0; i < shelves.size(); i++) {
int sum = 0;
for (int j : result[i]) {
sum += j;
}
if (sum + herb <= shelves[i]) {
result[i].push_back(herb);
break;
}
}
}
return result;
}
};import java.util.Arrays;
public class Solution {
public int[][] solution(int[] herbs, int[] shelves) {
Arrays.sort(herbs);
reverse(herbs);
int[][] result = new int[shelves.length][];
for (int i = 0; i < shelves.length; i++) {
result[i] = new int[0];
}
for (int herb : herbs) {
for (int i = 0; i < shelves.length; i++) {
int sum = 0;
for (int j : result[i]) {
sum += j;
}
if (sum + herb <= shelves[i]) {
int[] temp = new int[result[i].length + 1];
System.arraycopy(result[i], 0, temp, 0, result[i].length);
temp[temp.length - 1] = herb;
result[i] = temp;
break;
}
}
}
return result;
}
public void reverse(int[] array) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
}def solution(herbs, shelves):
herbs.sort(reverse=True)
result = [[] for _ in range(len(shelves))]
for herb in herbs:
for i in range(len(shelves)):
if sum(result[i]) + herb <= shelves[i]:
result[i].append(herb)
break
return resultfunction solution(herbs, shelves) {
herbs.sort((a, b) => b - a);
const result = [];
for (let i = 0; i < shelves.length; i++) {
result.push([]);
}
for (let herb of herbs) {
for (let i = 0; i < shelves.length; i++) {
let sum = result[i].reduce((a, b) => a + b, 0);
if (sum + herb <= shelves[i]) {
result[i].push(herb);
break;
}
}
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.