Maximize Supply Allocation — Problem Statement & Solution Guide
Problem Description
Given two arrays of integers, supplies and demands, determine the maximum total supply that can be allocated to meet the demands while minimizing excess supply. The supplies and demands should be sorted in descending and ascending order respectively before allocation.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximize Supply Allocation"
WHY DOES IT MATTER?
The greedy two‑pointer pattern is essential because it transforms a combinatorial allocation problem into a linear scan, guaranteeing optimality with minimal computational overhead. It eliminates the need for exponential search or complex DP states, making the solution scalable to millions of items.
OPTIMIZATION CHALLENGE
The key insight is that once supplies and demands are sorted, the decision at each step is forced: a supply that cannot satisfy the current smallest demand will never satisfy any larger demand, so it can be discarded immediately. This reduces the problem to a single pass rather than exploring many combinations.
REAL-WORLD CONNECTION
Consider a warehouse dispatch system where large pallets (supplies) must be matched to delivery trucks (demands). Assigning the biggest pallet to the smallest truck that can carry it prevents over‑packing and ensures efficient use of space, analogous to minimizing excess supply in the algorithm.
When explaining this pattern in an interview, emphasize the invariant that the remaining supplies are always sorted and that the current demand is the smallest unmet one. This clarity helps the interviewer see why the greedy choice is safe and optimal.
COMPLEXITY AT A GLANCE
O(n log n)O(1)Core Theory — Why This Approach?
The problem reduces to a classic greedy matching scenario: we have a multiset of supply units and a multiset of demand thresholds. By sorting supplies in descending order and demands in ascending order, we can iteratively pair the largest available supply with the smallest unmet demand. This ensures that each allocation uses the minimal excess supply necessary to satisfy a demand, thereby maximizing the total allocated supply while keeping leftover supply minimal.
A naive approach would attempt to explore all possible allocations, perhaps via backtracking or dynamic programming, leading to exponential or quadratic time complexity and quickly becoming infeasible for large input sizes. Such exhaustive methods also fail to guarantee optimality when the greedy choice is not locally optimal.
The optimal paradigm is a two‑pointer greedy algorithm: after sorting, we maintain indices into the supplies and demands arrays. At each step we compare the current supply with the current demand; if the supply meets or exceeds the demand, we allocate it, advance both pointers, and add the supply to the total. If it does not, we discard the supply (since it cannot satisfy any remaining demand) and advance the supply pointer only. This runs in O(n log n) time due to sorting and O(1) additional space, and it is provably optimal because any deviation from the greedy choice would either leave a demand unmet or waste a larger supply on a smaller demand, both of which reduce the total allocated supply or increase excess.
Interview Questions on This Problem
Q1How would you modify this algorithm if supplies could be split fractionally to meet multiple demands?
If fractional splitting is allowed, the greedy strategy still applies: sort supplies descending and demands ascending, then allocate as much of the current supply as needed to satisfy the current demand, potentially splitting the supply across multiple demands. The algorithm becomes a simple linear scan where each supply is consumed until it is exhausted, ensuring optimality because splitting never increases excess.
Q2In a distributed system where supplies and demands are stored across shards, how would you design a scalable solution?
Each shard would locally sort its subset of supplies and demands, then perform a local two‑pointer pass to produce partial allocations and remaining unallocated supplies. A central coordinator would merge these partial results by performing a k‑way merge on the sorted lists, then run a final two‑pointer pass on the merged lists to produce the global optimal allocation, achieving O(n log k) time where k is the number of shards.
Q3What is the time complexity if you skip sorting and use a priority queue instead?
Using a max‑heap for supplies and a min‑heap for demands, you can pop the largest supply and smallest demand in O(log n) each. The overall complexity becomes O(n log n) for heap operations, matching the sorting approach, but with higher constant factors and additional space for the heaps.
Examples
Input
[30, 20, 10], [5, 15, 25]
Output
45
Explanation: Step-by-step: sort supplies in descending order and demands in ascending order. Then, allocate the largest supply to the smallest demand until the demand is met or the supply is exhausted. In this case, the first supply of 30 is allocated to the first demand of 5, the second supply of 20 is allocated to the second demand of 15, and the third supply of 10 is allocated to the third demand of 25. The total supply allocated is 30 + 20 + 10 = 60, but the total demand is 5 + 15 + 25 = 45. So, the maximum total supply that can be allocated is 45.
Input
[60, 50, 40], [20, 30, 40]
Output
90
Explanation: Step-by-step: sort supplies in descending order and demands in ascending order. Then, allocate the largest supply to the smallest demand until the demand is met or the supply is exhausted. In this case, the first supply of 60 is allocated to the first demand of 20, the second supply of 50 is allocated to the second demand of 30, and the third supply of 40 is allocated to the third demand of 40. The total supply allocated is 60 + 50 + 40 = 150, but the total demand is 20 + 30 + 40 = 90. So, the maximum total supply that can be allocated is 90.
Constraints
- 1 <= supplies.length <= 1000
- 1 <= demands.length <= 1000
- 1 <= supplies[i] <= 10^4
- 1 <= demands[j] <= 10^4
- The total supply is greater than or equal to the total demand
Optimal Approach & Strategy
Sort supplies descending and demands ascending, then use a two‑pointer greedy scan to allocate supplies to demands, achieving O(n log n) time and O(1) extra space.
Brute Force Approach
Try every possible pairing of supplies to demands, checking all combinations to find the maximum total allocation. This leads to exponential time complexity and is impractical for large inputs.
Verified Code Solutions
function maxSupplyAllocation(supplies, demands) {
supplies.sort((a, b) => b - a);
demands.sort((a, b) => a - b);
let totalSupply = 0;
for (let i = 0; i < supplies.length; i++) {
for (let j = 0; j < demands.length; j++) {
if (demands[j] > 0) {
let allocated = Math.min(supplies[i], demands[j]);
totalSupply += allocated;
supplies[i] -= allocated;
demands[j] -= allocated;
}
}
}
return totalSupply;
}class Solution {
public:
int maxSupplyAllocation(vector<int>& supplies, vector<int>& demands) {
sort(supplies.rbegin(), supplies.rend());
sort(demands.begin(), demands.end());
int totalSupply = 0;
for (int i = 0; i < supplies.size(); i++) {
for (int j = 0; j < demands.size(); j++) {
if (demands[j] > 0) {
int allocated = min(supplies[i], demands[j]);
totalSupply += allocated;
supplies[i] -= allocated;
demands[j] -= allocated;
}
}
}
return totalSupply;
}
}class Solution {
public int maxSupplyAllocation(int[] supplies, int[] demands) {
Arrays.sort(supplies);
Arrays.sort(demands);
int totalSupply = 0;
for (int i = supplies.length - 1; i >= 0; i--) {
for (int j = 0; j < demands.length; j++) {
if (demands[j] > 0) {
int allocated = Math.min(supplies[i], demands[j]);
totalSupply += allocated;
supplies[i] -= allocated;
demands[j] -= allocated;
}
}
}
return totalSupply;
}
}def max_supply_allocation(supplies, demands):
supplies.sort(reverse=True)
demands.sort()
total_supply = 0
for i in range(len(supplies)):
for j in range(len(demands)):
if demands[j] > 0:
allocated = min(supplies[i], demands[j])
total_supply += allocated
supplies[i] -= allocated
demands[j] -= allocated
return total_supplyfunction maxSupplyAllocation(supplies, demands) {
supplies.sort((a, b) => b - a);
demands.sort((a, b) => a - b);
let totalSupply = 0;
for (let i = 0; i < supplies.length; i++) {
for (let j = 0; j < demands.length; j++) {
if (demands[j] > 0) {
let allocated = Math.min(supplies[i], demands[j]);
totalSupply += allocated;
supplies[i] -= allocated;
demands[j] -= allocated;
}
}
}
return totalSupply;
}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.