Skip to main content
Talentd

Distribute Repeating Integers - Solution & Explanation

HardArrayDynamic ProgrammingBacktrackingBit Manipulation15 min readAsked at: Google
Practice this problem

Problem Statement

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:

  • The ith customer gets exactly quantity[i] integers,
  • The integers the ith customer gets are all equal, and
  • Every customer is satisfied.

Return 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.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= 1000
  • m == quantity.length
  • 1 <= m <= 10
  • 1 <= quantity[i] <= 105
  • There are at most 50 unique values in nums.

Approach Overview

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 1: Backtracking Approach

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

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.

Code

JavaScript

JavaScript

Complexity

Time Complexity: O(50 * 2^m), as we evaluate possible states over order combinations.
Space Complexity: O(2^m), for DP table storage.

Try this approach in the editor →

Approach 3: State Compression Dynamic Programming + Subset Enumeration

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(50 + m) due to the recursive stack and frequency counter.

Dynamic Programming Approach

Time Complexity: O(50 * 2^m), as we evaluate possible states over order combinations.
Space Complexity: O(2^m), for DP table storage.

State Compression Dynamic Programming + Subset Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Frequency MatchingO(k^m) worst caseO(k)When the number of customers is small and pruning with sorted requests is effective
Bitmask Dynamic ProgrammingO(n * 2^m * m)O(n * 2^m)General optimized solution when customers ≤ 10 and subset DP is feasible

Video Solution

花花酱 LeetCode 1655. Distribute Repeating Integers - 刷题找工作 EP370 • Hua Hua • 2,242 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Distribute Repeating Integers easy or hard?
Distribute Repeating Integers is classified as a Hard problem on LeetCode with an acceptance rate around 40%. The challenge comes from modeling the assignment of requests to frequency buckets and optimizing the search using pruning or subset dynamic programming.
Distribute Repeating Integers Python/Java solution
Python and C++ implementations typically use recursive backtracking with sorted request arrays and frequency counts. JavaScript implementations often use bitmask dynamic programming where dp[i][mask] tracks whether the first i frequencies can satisfy a subset of customers.
How to solve Distribute Repeating Integers in O(n)?
An O(n) solution is not possible because the problem requires exploring combinations of customer requests. The practical optimal method uses bitmask dynamic programming over customer subsets with complexity O(n * 2^m * m), which is efficient since m is usually ≤ 10.
What is the best approach for Distribute Repeating Integers?
The most reliable approach uses bitmask dynamic programming. Precompute the demand of every subset of customers and assign those subsets to number frequencies. This reduces repeated exploration compared to naive recursion and runs in O(n * 2^m * m) time where m is the number of customers.
Is Distribute Repeating Integers asked at Google/Amazon/Meta?
Problems involving frequency distribution, subset assignment, and bitmask DP frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests backtracking optimization and subset dynamic programming, both common patterns in senior-level interview rounds.
What data structure is used in Distribute Repeating Integers?
The solution relies on frequency maps or arrays to count occurrences of each integer, combined with bitmasks to represent subsets of customers. Dynamic programming tables or recursive backtracking stacks track which requests have been satisfied.
What is the time complexity of Distribute Repeating Integers?
The optimized bitmask DP solution runs in O(n * 2^m * m) time and O(n * 2^m) space, where n is the number of unique integer values and m is the number of customers. A simpler backtracking approach can degrade to roughly O(k^m) in the worst case but works well with pruning when m is small.

Ready to solve this problem?

Practice Distribute Repeating Integers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays