Distribute Repeating Integers

Hard
1584.

Distribute Repeating Integers

Distribute Repeating Integers is a hard coding problem on arrays, dynamic programming and backtracking, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} quantity
 * @return {boolean}
 */
var canDistribute = function(nums, quantity) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Distribute Repeating Integers — Problem & Solution

Distribute Repeating Integers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Distribute Repeating Integers is a hard coding problem on arrays, dynamic programming and backtracking, asked in Amazon and Google interviews.

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

Hints for Distribute Repeating Integers

  1. Hint 1

    Only how many copies each value has matters, not the values themselves.

  2. Hint 2

    There are at most 10 customers. Try to serve them one at a time, choosing which value's stock each one draws from.

  3. Hint 3

    Serve the largest orders first so dead ends appear early, and when two values have the same remaining stock, trying both is redundant — try only one.

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)

Java

public static boolean canDistribute(int[] nums, int[] quantity) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int v : nums) freq.merge(v, 1, Integer::sum);
    int[] counts = new int[freq.size()];
    int idx = 0;
    for (int c : freq.values()) counts[idx++] = c;
    int[] q = quantity.clone();
    Arrays.sort(q);
    for (int l = 0, r = q.length - 1; l < r; l++, r--) { int t = q[l]; q[l] = q[r]; q[r] = t; }
    return distDfs(counts, q, 0);
}

static boolean distDfs(int[] counts, int[] q, int i) {
    if (i == q.length) return true;
    for (int j = 0; j < counts.length; j++) {
        if (counts[j] < q[i]) continue;
        boolean dup = false;
        for (int t = 0; t < j; t++) if (counts[t] == counts[j]) { dup = true; break; }
        if (dup) continue;
        counts[j] -= q[i];
        if (distDfs(counts, q, i + 1)) return true;
        counts[j] += q[i];
    }
    return false;
}

C++

bool distDfs(vector<int>& counts, vector<int>& q, int i) {
    if (i == (int)q.size()) return true;
    for (int j = 0; j < (int)counts.size(); j++) {
        if (counts[j] < q[i]) continue;
        bool dup = false;
        for (int t = 0; t < j; t++) if (counts[t] == counts[j]) { dup = true; break; }
        if (dup) continue;
        counts[j] -= q[i];
        if (distDfs(counts, q, i + 1)) return true;
        counts[j] += q[i];
    }
    return false;
}

bool canDistribute(vector<int>& nums, vector<int>& quantity) {
    map<int, int> freq;
    for (int v : nums) freq[v]++;
    vector<int> counts;
    for (auto& p : freq) counts.push_back(p.second);
    vector<int> q(quantity.begin(), quantity.end());
    sort(q.rbegin(), q.rend());
    return distDfs(counts, q, 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming