Get started

Distribute Repeating Integers — Hard Problem & Solution

A warehouse holds the integers in nums (at most 50 distinct values, each possibly repeated many times).

Problem statement

A warehouse holds the integers in nums (at most 50 distinct values, each possibly repeated many times). There are m customers; customer i wants exactly quantity[i] integers, and all the integers one customer receives must be equal to each other. Each integer in nums can be given to at most one customer, and some may be left over.

Return true if every customer can be satisfied at the same time.

Example 1

Input: nums = [4,4,4,9,9], quantity = [2,2]
Output: true
Explanation: One customer gets `[4,4]`, the other `[9,9]`.

Example 2

Input: nums = [1,2,3,3], quantity = [2,2]
Output: false
Explanation: Only the value 3 appears twice, and it cannot serve both customers.

Example 3

Input: nums = [5,5,5,5,5,5], quantity = [3,1,2]
Output: true
Explanation: All three customers take 5s: 3 + 1 + 2 = 6.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 1000
  • There are at most 50 distinct values in nums
  • 1 <= quantity.length <= 10
  • 1 <= quantity[i] <= 10^5

How to solve Distribute Repeating Integers

Reduce nums to the multiset of stock counts, then backtrack over customers, largest order first, assigning each to a value whose remaining stock can cover it. Interchangeable stocks (equal remaining counts) are tried once.

Approach

  1. Count each distinct value; keep only the counts.
  2. Sort quantity in decreasing order.
  3. dfs(i): if i == m, succeed. For each stock j with count[j] >= quantity[i] whose current count differs from every earlier stock's, subtract, recurse on i + 1, and add back.
  4. Return dfs(0).

Why it works

Every valid distribution assigns each customer to one value with enough stock, which is exactly what the search enumerates. Two stocks with the same remaining count are interchangeable for all later customers, so skipping the second one discards only mirror images of branches already explored. A bitmask DP over subsets of customers (O(k · 3^m)) proves the same answer and is the alternative when the search space is adversarial.

Complexity

  • Time — O(k^m) worst case for k distinct values; tiny in practice. The subset DP is O(k · 3^m).
  • Space — O(k + m)

Pitfalls

  • A customer's integers must all be the same value — you cannot split one order across two values.
  • Several customers may share one value as long as its count covers all of them.
  • Sorting the orders in decreasing order matters for speed, not for correctness.

Reference solution

Python

from typing import List

def canDistribute(nums: List[int], quantity: List[int]) -> bool:
    freq = {}
    for v in nums:
        freq[v] = freq.get(v, 0) + 1
    counts = sorted(freq.values(), reverse=True)
    q = sorted(quantity, reverse=True)
    m = len(q)

    def dfs(i):
        if i == m:
            return True
        for j in range(len(counts)):
            if counts[j] < q[i]:
                continue
            if any(counts[t] == counts[j] for t in range(j)):
                continue
            counts[j] -= q[i]
            if dfs(i + 1):
                return True
            counts[j] += q[i]
        return False

    return dfs(0)

JavaScript

var canDistribute = function(nums, quantity) {
    var freq = new Map();
    for (var i = 0; i < nums.length; i++) freq.set(nums[i], (freq.get(nums[i]) || 0) + 1);
    var counts = Array.from(freq.values()).sort(function(a, b) { return b - a; });
    var q = quantity.slice().sort(function(a, b) { return b - a; });
    var dfs = function(i) {
        if (i === q.length) return true;
        for (var j = 0; j < counts.length; j++) {
            if (counts[j] < q[i]) continue;
            var dup = false;
            for (var t = 0; t < j; t++) if (counts[t] === counts[j]) { dup = true; break; }
            if (dup) continue;
            counts[j] -= q[i];
            if (dfs(i + 1)) return true;
            counts[j] += q[i];
        }
        return false;
    };
    return dfs(0);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming