Watch 6 video solutions for Distribute Repeating Integers, a hard level problem involving Array, Dynamic Programming, Backtracking. This walkthrough by Hua Hua has 2,239 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the ith customer ordered. Determine if it is possible to distribute nums such that:
ith customer gets exactly quantity[i] integers,ith customer gets are all equal, andReturn true if it is possible to distribute nums according to the above conditions.
Example 1:
Input: nums = [1,2,3,4], quantity = [2] Output: false Explanation: The 0th customer cannot be given two different integers.
Example 2:
Input: nums = [1,2,3,3], quantity = [2] Output: true Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.
Example 3:
Input: nums = [1,1,2,2], quantity = [2,2] Output: true Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].
Constraints:
n == nums.length1 <= n <= 1051 <= nums[i] <= 1000m == quantity.length1 <= m <= 101 <= quantity[i] <= 10550 unique values in nums.Problem Overview: You receive an array of integers where values may repeat, and a list of customer quantity requests. Each customer must receive exactly the number of integers they request, and all integers given to a customer must have the same value. The task is to determine whether the available frequencies of numbers can satisfy every request.
Approach 1: Backtracking with Frequency Matching (Exponential, practical for small m)
First count the frequency of each number using a hash map or frequency array from the array. Customers only care about counts, not actual values. Sort the request quantities in descending order so larger demands are handled first, which prunes failing branches earlier. During recursion, try assigning each request to any remaining frequency bucket that can satisfy it, subtract the quantity, recurse, and backtrack if it fails. This search explores possible assignments of requests to value frequencies. Time complexity is roughly O(k^m) in the worst case (k unique numbers, m customers), with O(k) space for recursion and frequency tracking.
Approach 2: Bitmask Dynamic Programming (O(n * 2^m * m))
Dynamic programming improves the brute-force search by grouping customer assignments using a bitmask. Let m be the number of customers. Precompute the total quantity required for every subset of customers represented by a bitmask. Then iterate through each number frequency and decide which subset of customers it can satisfy. The DP state dp[i][mask] means whether the first i frequencies can fulfill the set of customers represented by mask. For each state, try assigning a submask of remaining customers whose total demand does not exceed the current frequency. This converts many repeated backtracking checks into cached transitions. Time complexity is O(n * 2^m * m) and space complexity is O(n * 2^m), where n is the number of unique values. This approach relies heavily on dynamic programming and subset enumeration.
Recommended for interviews: The backtracking solution usually comes first in interviews because it directly models assigning requests to available frequencies. Sorting requests and pruning branches shows strong problem-solving instincts. The bitmask DP approach demonstrates deeper optimization skills and knowledge of subset DP, which interviewers often expect for Hard problems with small constraint sizes.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Frequency Matching | O(k^m) worst case | O(k) | When the number of customers is small and pruning with sorted requests is effective |
| Bitmask Dynamic Programming | O(n * 2^m * m) | O(n * 2^m) | General optimized solution when customers ≤ 10 and subset DP is feasible |