Supply Allocation Optimization — Problem Statement & Solution Guide

GreedyMediumMixed

TimeO(N log N)

SpaceO(1) additional

Problem Description

You are given a list of supply sources, each with a limited capacity, and a list of demand centers, each with a specific demand. Determine the optimal way to allocate supplies from the sources to the demand centers to maximize the number of fully supplied demand centers. The allocation strategy should prioritize supplying the demand centers with the highest demand first. If the total supply is less than the total demand, return -1 or handle this case according to the problem requirements.

DSA Pattern Breakdown

"Supply Allocation Optimization"

medium

WHY DOES IT MATTER?

This pattern exemplifies the classic greedy‑first‑fit allocation, a cornerstone in capacity planning, load balancing, and inventory management where decisions must be made quickly under limited resources.

OPTIMIZATION CHALLENGE

The key insight is recognizing that sorting demands once gives a global priority order, eliminating the need for repeated searches or complex DP; the remaining supply can be tracked with a single accumulator.

REAL-WORLD CONNECTION

Think of a warehouse distributing limited stock to retail stores: the stores with the biggest orders are prioritized to ensure high‑value contracts are honored before smaller ones, mirroring the algorithm's ordering.

During an interview, implement the sort first, then use a simple loop with a running supply counter—avoid over‑engineering with priority queues or backtracking, which adds unnecessary complexity.

COMPLEXITY AT A GLANCE

⏱ Time:O(N log N)

💾 Space:O(1) additional

Core Theory — Why This Approach?

The problem reduces to a resource‑allocation variant where we have a total supply equal to the sum of all source capacities and a list of demand values. The objective is to maximize the count of demand centers that receive their full requirement, with a strict priority on the highest‑demand centers. A naive solution would try every subset of demands or simulate all possible distributions among sources, leading to exponential time. The optimal paradigm leverages a greedy strategy: sort the demand centers in descending order and iteratively satisfy each demand using the remaining aggregate supply. Because we always allocate to the largest unmet demand first, any alternative allocation that satisfies a smaller demand while leaving a larger one unsatisfied would never increase the total number of fully supplied centers, proving the greedy choice optimal. This approach runs in O(N log N) due to sorting, and O(1) additional space beyond the input arrays.

Interview Questions on This Problem

Q1How would you modify the algorithm if each supply source could only serve a contiguous block of demand centers?

Introduce a two‑pointer or sliding‑window technique on the sorted demand list, while maintaining a prefix sum of supplies per source. For each source, allocate to the longest possible contiguous segment that fits within its capacity, then move to the next source. This preserves O(N log N) sorting and adds O(N) linear scanning.

Q2Explain why a max‑heap is not necessary for this problem, even though we prioritize highest demand first.

A max‑heap would give O(log N) per extraction, but we only need a single global ordering of demands. Sorting once yields the same order with O(N log N) total cost, and subsequent linear scans are O(1) per demand, making the heap overhead unnecessary.

Q3If the total supply is less than the smallest demand, what should the algorithm return and why?

It should return zero fully supplied demand centers because no demand can be satisfied completely. The greedy loop will terminate immediately when the remaining supply is insufficient for the current (largest) demand, correctly yielding a count of zero.

Examples

Example 1

Input

[[1, 2, 3], [4, 5, 6]], [[6, 15]]

Output

Explanation: With the given supply sources [[1, 2, 3], [4, 5, 6]] and demand centers [[6, 15]], the optimal allocation would be to supply the first demand center with the sum of the first supply source (1+2+3=6), which fully supplies the first demand center, leaving the second demand center unsupplied due to insufficient total supply.

Example 2

Input

[[1, 2], [3, 4], [5, 6]], [[2, 2, 2]]

Output

Explanation: Given the supply sources [[1, 2], [3, 4], [5, 6]] and demand centers [[2, 2, 2]], the optimal allocation would involve distributing supplies from each source to each demand center in a way that maximizes the number of fully supplied demand centers. However, without a clear allocation strategy defined in the problem statement, the exact distribution cannot be determined.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Optimal Approach & Strategy

Sort demands descending, then greedily allocate from the total supply until a demand cannot be met, counting satisfied centers; this runs in O(N log N).

Brute Force Approach

Try every possible subset of demand centers, checking if the sum of their demands is ≤ total supply, and keep the largest subset size; this is exponential.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N log N)

function solution(supplySources, demandCenters) {
      // Sort supply sources and demand centers in descending order
      supplySources.sort((a, b) => b.reduce((x, y) => x + y, 0) - a.reduce((x, y) => x + y, 0));
      demandCenters.sort((a, b) => b - a);
      
      let totalSupply = supplySources.reduce((acc, curr) => acc + curr.reduce((x, y) => x + y, 0), 0);
      let totalDemand = demandCenters.reduce((x, y) => x + y, 0);
      
      if (totalSupply < totalDemand) {
         return -1; // or handle this case according to the problem requirements
      }
      
      let fullySupplied = 0;
      let remainingDemand = demandCenters.slice();
      
      for (let source of supplySources) {
         for (let supply of source) {
            for (let i = 0; i < remainingDemand.length; i++) {
               if (remainingDemand[i] <= supply) {
                  fullySupplied++;
                  remainingDemand.splice(i, 1);
                  break;
               } else {
                  remainingDemand[i] -= supply;
               }
            }
         }
      }
      
      return fullySupplied;
   }

class Solution {
   public:
       int solution(vector<vector<int>>& supplySources, vector<int>& demandCenters) {
           // Sort supply sources and demand centers in descending order
           sort(supplySources.begin(), supplySources.end(), [](const vector<int>& a, const vector<int>& b) {
               return accumulate(a.begin(), a.end(), 0) > accumulate(b.begin(), b.end(), 0);
           });
           sort(demandCenters.begin(), demandCenters.end(), greater<int>());
           
           int totalSupply = 0;
           for (const auto& source : supplySources) {
               for (int supply : source) {
                   totalSupply += supply;
               }
           }
           int totalDemand = 0;
           for (int demand : demandCenters) {
               totalDemand += demand;
           }
           
           if (totalSupply < totalDemand) {
               return -1; // or handle this case according to the problem requirements
           }
           
           int fullySupplied = 0;
           vector<int> remainingDemand = demandCenters;
           
           for (const auto& source : supplySources) {
               for (int supply : source) {
                   for (int i = 0; i < remainingDemand.size(); i++) {
                       if (remainingDemand[i] <= supply) {
                           fullySupplied++;
                           remainingDemand.erase(remainingDemand.begin() + i);
                           break;
                       } else {
                           remainingDemand[i] -= supply;
                       }
                   }
               }
           }
           
           return fullySupplied;
       }
   };

class Solution {
      public int solution(int[][] supplySources, int[] demandCenters) {
         // Sort supply sources and demand centers in descending order
         Arrays.sort(supplySources, (a, b) -> Integer.compare(sum(b), sum(a)));
         Arrays.sort(demandCenters);
         reverse(demandCenters);
         
         int totalSupply = 0;
         for (int[] source : supplySources) {
            for (int supply : source) {
               totalSupply += supply;
            }
         }
         int totalDemand = 0;
         for (int demand : demandCenters) {
            totalDemand += demand;
         }
         
         if (totalSupply < totalDemand) {
            return -1; // or handle this case according to the problem requirements
         }
         
         int fullySupplied = 0;
         int[] remainingDemand = demandCenters.clone();
         
         for (int[] source : supplySources) {
            for (int supply : source) {
               for (int i = 0; i < remainingDemand.length; i++) {
                  if (remainingDemand[i] <= supply) {
                     fullySupplied++;
                     remainingDemand = removeAt(remainingDemand, i);
                     break;
                  } else {
                     remainingDemand[i] -= supply;
                  }
               }
            }
         }
         
         return fullySupplied;
      }
      
      private int sum(int[] array) {
         int sum = 0;
         for (int value : array) {
            sum += value;
         }
         return sum;
      }
      
      private 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--;
         }
      }
      
      private int[] removeAt(int[] array, int index) {
         int[] result = new int[array.length - 1];
         System.arraycopy(array, 0, result, 0, index);
         System.arraycopy(array, index + 1, result, index, array.length - index - 1);
         return result;
      }
   }

def solution(supplySources, demandCenters):
      # Sort supply sources and demand centers in descending order
      supplySources.sort(key=sum, reverse=True)
      demandCenters.sort(reverse=True)
      
      totalSupply = sum(sum(source) for source in supplySources)
      totalDemand = sum(demandCenters)
      
      if totalSupply < totalDemand:
         return -1  # or handle this case according to the problem requirements
      
      fullySupplied = 0
      remainingDemand = demandCenters[:]
      
      for source in supplySources:
         for supply in source:
            for i in range(len(remainingDemand)):
               if remainingDemand[i] <= supply:
                  fullySupplied += 1
                  remainingDemand.pop(i)
                  break
               else:
                  remainingDemand[i] -= supply
      
      return fullySupplied

function solution(supplySources, demandCenters) {
      // Sort supply sources and demand centers in descending order
      supplySources.sort((a, b) => b.reduce((x, y) => x + y, 0) - a.reduce((x, y) => x + y, 0));
      demandCenters.sort((a, b) => b - a);
      
      let totalSupply = supplySources.reduce((acc, curr) => acc + curr.reduce((x, y) => x + y, 0), 0);
      let totalDemand = demandCenters.reduce((x, y) => x + y, 0);
      
      if (totalSupply < totalDemand) {
         return -1; // or handle this case according to the problem requirements
      }
      
      let fullySupplied = 0;
      let remainingDemand = demandCenters.slice();
      
      for (let source of supplySources) {
         for (let supply of source) {
            for (let i = 0; i < remainingDemand.length; i++) {
               if (remainingDemand[i] <= supply) {
                  fullySupplied++;
                  remainingDemand.splice(i, 1);
                  break;
               } else {
                  remainingDemand[i] -= supply;
               }
            }
         }
      }
      
      return fullySupplied;
   }

Asked in Top Tech Interviews

uncategorizedmediumgeneric

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.

Supply Allocation Optimization Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Greedy

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Supply Allocation Optimization — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor