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.
In this approach, use a backtracking algorithm to attempt assigning quantities to customers. You'll iterate over each unique integer and attempt to fulfill as many customer orders as possible with that integer's frequency. If any assignment fails, backtrack and try a different distribution.
This Python solution initializes a frequency counter for each unique integer in nums. It defines a recursive backtrack function to try fitting each customer's quantity using any available number's frequency. Frequency is reduced when a fit is attempted and restored on failure to explore other possibilities.
Time Complexity: O(m * 50^m), where 'm' is the number of orders and '50' is the maximum number of unique integers. In the worst case, we try all combinations of orders.
Space Complexity: O(50 + m) due to the recursive stack and frequency counter.
Leveraging dynamic programming, create a state representation for each combination of orders to minimize and accurately track required integers. Use a bitmask for denoting which customer orders have been completed and update the algorithm’s state as combinations are validly formed.
This JavaScript solution populates a dynamic programming table where each state is a bitmask representing complete status of customer orders. For each number, possible matches are tested, updating the DP table with new states as they reach a valid completion threshold.
JavaScript
Time Complexity: O(50 * 2^m), as we evaluate possible states over order combinations.
Space Complexity: O(2^m), for DP table storage.
First, we count the occurrence of each number in the array nums, and record it in the hash table cnt. Then we store the values in the hash table into the array arr. We denote the length of the array arr as n.
Note that the length of the array quantity does not exceed 10, so we can use a binary number to represent a subset of quantity. That is, the number j represents a subset of quantity, where the i-th bit of the binary representation of j is 1 means the i-th number in quantity is selected, and 0 means the i-th number is not selected.
We can preprocess an array s, where s[j] represents the sum of all numbers in the subset j of quantity.
Next, we define f[i][j] to represent whether the numbers in arr[0,..i-1] can be successfully allocated to the subset j of quantity, where i ranges from [0,..n-1], and j ranges from [0,2^m-1], where m is the length of quantity.
Considering f[i][j], if there exists a subset k in j such that s[k] <= arr[i], and f[i-1][j XOR k] is true, then f[i][j] is true, otherwise f[i][j] is false.
The answer is f[n-1][2^m-1].
The time complexity is O(n * 3^m), and the space complexity is O(n * 2^m). Here, n is the number of different integers in the array nums, and m is the length of the array quantity.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(m * 50^m), where 'm' is the number of orders and '50' is the maximum number of unique integers. In the worst case, we try all combinations of orders. |
| Dynamic Programming Approach | Time Complexity: O(50 * 2^m), as we evaluate possible states over order combinations. |
| State Compression Dynamic Programming + Subset Enumeration | — |
| 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 |
花花酱 LeetCode 1655. Distribute Repeating Integers - 刷题找工作 EP370 • Hua Hua • 2,239 views views
Watch 5 more video solutions →Practice Distribute Repeating Integers with our built-in code editor and test cases.
Practice on FleetCode