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.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Backtracking, Bitmask
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^51 <= nums[i] <= 1000There are at most 50 distinct values in nums1 <= quantity.length <= 101 <= quantity[i] <= 10^5
Hints for Distribute Repeating Integers
Hint 1
Only how many copies each value has matters, not the values themselves.
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.
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
- Count each distinct value; keep only the counts.
- Sort
quantityin decreasing order. dfs(i): ifi == m, succeed. For each stockjwithcount[j] >= quantity[i]whose current count differs from every earlier stock's, subtract, recurse oni + 1, and add back.- 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