#1655

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Distribute Repeating Integers

Determine if you can allocate integers to satisfy customer quantities using state transition dynamic programming techniques efficiently.

array dynamic programming backtracking bit manipulation bitmask

Problem Statement

You are given an array nums of n integers, where at most 50 unique values exist, and an array quantity of m customer orders. Each quantity[i] specifies how many identical integers the ith customer requests. Determine if it's possible to assign integers from nums so that each customer receives exactly quantity[i] of identical numbers without sharing integers across customers.

Return true if such a distribution exists. For example, nums = [1,2,3,4], quantity = [2] returns false since no customer can get two identical numbers, while nums = [1,1,2,2], quantity = [2,2] returns true as each customer can receive a matching pair.

Examples

Example 1

Input: nums = [1,2,3,4], quantity = [2]

Output: false

The 0th customer cannot be given two different integers.

Example 2

Input: nums = [1,2,3,3], quantity = [2]

Output: true

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

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.

Solution Approach

Count Frequencies

Calculate the frequency of each unique number in nums. For example, nums = [4,4,5,5,5] gives frequencies [2,3]. This allows mapping available integers to customer requests efficiently.

Use State Transition DP with Bitmask

Apply dynamic programming with bitmasking to represent which customers have been satisfied. Each DP state corresponds to a subset of customers, and transitions allocate available numbers to unfulfilled orders while pruning impossible combinations.

Recursive Backtracking with Pruning

Combine DP with backtracking to attempt distributions. Recursively assign frequencies to remaining customers, skipping paths where a frequency is insufficient. This leverages both the limited unique numbers and small customer count to reduce computation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of unique numbers and customer orders, roughly O(2^m * n) in the worst case due to all DP states. Space complexity is O(2^m) for storing DP states.

What Interviewers Usually Probe

Counting frequencies before attempting assignment indicates understanding of data reduction for DP.
Implementing bitmask DP shows awareness of handling subsets efficiently in state transition problems.
Pruning impossible paths during backtracking signals optimization for hard cases with repeated numbers.

Common Pitfalls or Variants

Common pitfalls

Failing to account for identical numbers and giving a customer distinct integers instead.
Overlooking pruning opportunities, leading to TLE for larger frequency distributions.
Incorrectly initializing DP states, causing invalid assignments to propagate.

Follow-up variants

Distribute integers allowing each customer to receive either one or two identical numbers.
Maximize the number of customers satisfied given limited repeated integers in nums.
Distribute integers with constraints on specific integer types per customer.

FAQ

What is the main pattern used in Distribute Repeating Integers?

The problem relies on state transition dynamic programming, tracking subsets of satisfied customers via bitmasking.

How do frequencies of nums help in solving this problem?

Counting frequencies reduces the search space by letting you know exactly how many of each number are available for allocation.

Why is backtracking needed along with DP?

Backtracking allows trying different allocation orders of numbers to customers while DP avoids recomputing identical states.

What causes a false return in example inputs?

If a customer’s requested quantity cannot be fulfilled with identical numbers from nums, the function returns false.

Can this approach scale for large n?

Yes, because DP operates on at most 50 unique numbers and up to 10 customers, keeping computation feasible even if n is large.

terminal

Solution

Solution 1: 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`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class Solution:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
        m = len(quantity)
        s = [0] * (1 << m)
        for i in range(1, 1 << m):
            for j in range(m):
                if i >> j & 1:
                    s[i] = s[i ^ (1 << j)] + quantity[j]
                    break
        cnt = Counter(nums)
        arr = list(cnt.values())
        n = len(arr)
        f = [[False] * (1 << m) for _ in range(n)]
        for i in range(n):
            f[i][0] = True
        for i, x in enumerate(arr):
            for j in range(1, 1 << m):
                if i and f[i - 1][j]:
                    f[i][j] = True
                    continue
                k = j
                while k:
                    ok1 = j == k if i == 0 else f[i - 1][j ^ k]
                    ok2 = s[k] <= x
                    if ok1 and ok2:
                        f[i][j] = True
                        break
                    k = (k - 1) & j
        return f[-1][-1]

Continue Practicing

#1723 find minimum time to finish all jobs #1799 maximize score after n operations #1947 maximum compatibility score sum