LeetCode 1655 - Distribute Repeating Integers

This problem asks whether we can satisfy a set of customer requests using repeated integers from the array nums. Each customer wants a certain quantity of numbers, given by quantity[i]. The important restriction is that every number given to a single customer must be identical.

leetcodehardarrayhash-tabledynamic-programmingbacktrackingbit-manipulationcountingbitmask

LeetCode Problem 1655

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Dynamic Programming, Backtracking, Bit Manipulation, Counting, Bitmask

Solution

Problem Understanding

This problem asks whether we can satisfy a set of customer requests using repeated integers from the array nums.

Each customer wants a certain quantity of numbers, given by quantity[i]. The important restriction is that every number given to a single customer must be identical. A customer asking for 3 items cannot receive [1,2,1], they must receive something like [5,5,5].

The actual numeric values do not matter individually. What matters is how many times each value appears. For example:

  • nums = [1,1,1,2,2,3]

  • Frequencies are:

  • 1 -> 3

  • 2 -> 2

  • 3 -> 1

A customer requesting 2 items could be satisfied using value 1 or value 2, but not value 3.

The goal is to determine whether all customers can simultaneously be satisfied.

The constraints are very important:

  • nums.length can be as large as 100000
  • There are at most 50 unique values
  • quantity.length <= 10

The large size of nums suggests that iterating over the raw array repeatedly would be too expensive. However, the small number of customers is the key observation. Since there are at most 10 customers, we can use bitmask dynamic programming over subsets of customers.

The problem is fundamentally about assigning customer groups to frequency buckets.

Several edge cases are important:

  • A customer may request more items than any frequency can provide.
  • Multiple customers may need to share the same frequency bucket carefully.
  • Some values in nums may never be used.
  • Customers can receive the same numeric value only if the total allocated amount does not exceed that value's frequency.

For example:

  • nums = [1,1,1,1]
  • quantity = [2,2]

This works because both customers can receive value 1.

But:

  • nums = [1,1,1]
  • quantity = [2,2]

This fails because the total demand exceeds the available count.

Approaches

Brute Force Approach

A brute force solution would try every possible assignment of customers to integer values.

First, we count the frequency of each distinct value in nums. Then, for every customer, we attempt to assign them to one of the available frequencies that can satisfy their demand.

The recursion would look like:

  • Pick a customer
  • Try every frequency bucket that still has enough remaining count
  • Deduct the quantity
  • Continue recursively

This approach is correct because it explores all possible valid assignments.

However, it becomes extremely slow because the number of assignments grows exponentially. Even with only 10 customers and 50 distinct frequencies, the branching factor is enormous.

The brute force solution suffers from repeated recomputation of equivalent states.

Optimal Approach, Bitmask Dynamic Programming

The key insight is that the number of customers is very small, at most 10.

This means we can represent any subset of customers using a bitmask:

  • 0b00101 means customers 0 and 2 are included
  • Total subsets = 2^m
  • Since m <= 10, this is at most 1024

Instead of assigning customers one by one naively, we precompute:

  • The total quantity required for every subset of customers

Then, for each frequency bucket, we try assigning any subset of currently unserved customers that fits within that frequency.

This transforms the problem into a subset DP problem.

The DP state becomes:

  • Which customer subsets have already been satisfied

This dramatically reduces repeated work.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential, roughly O(k^m) O(m) Tries all assignments recursively
Optimal O(n * 3^m) O(2^m) Uses subset DP with bitmask optimization

Here:

  • k = number of unique values
  • m = number of customers

Since m <= 10, 3^m is manageable.

Algorithm Walkthrough

Step 1: Count Frequencies

We first count how many times each integer appears in nums.

For example:

nums = [1,1,1,2,2,3]

frequencies = [3,2,1]

The actual integer values are irrelevant after counting.

Step 2: Precompute Subset Sums

We represent customer subsets using bitmasks.

Suppose:

quantity = [2,3,1]

Then:

Mask Customers Sum
001 {0} 2
010 {1} 3
011 {0,1} 5
111 {0,1,2} 6

We store these sums in an array:

subset_sum[mask]

This allows constant time lookup of total demand for any subset.

Step 3: Define DP State

We define:

dp[mask]

Meaning:

  • Whether the subset mask of customers can be satisfied using processed frequencies so far.

Initially:

dp[0] = True

Because satisfying zero customers is always possible.

Step 4: Process Each Frequency

For every frequency count:

count

We create a new DP array.

For every current satisfied state:

mask

We try assigning additional unsatisfied customer subsets.

Step 5: Enumerate Subsets

Suppose:

remaining = full_mask ^ mask

This represents customers not yet satisfied.

We enumerate all submasks of remaining.

For each submask:

  • Compute required quantity
  • Check if it fits within the current frequency
subset_sum[submask] <= count

If valid:

new_mask = mask | submask

Mark it reachable.

Step 6: Return Final Result

If:

dp[full_mask]

is true, then all customers can be satisfied.

Otherwise, return false.

Why it works

The algorithm works because every DP state represents a complete and valid assignment for a subset of customers.

When processing a frequency bucket, we consider every possible subset of remaining customers that this bucket can satisfy. Since all subsets are explored systematically, no valid arrangement is missed.

The bitmask uniquely identifies which customers have already been satisfied, preventing duplicate recomputation of equivalent states.

Because each customer subset is considered exactly through DP transitions, the algorithm guarantees correctness.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
        frequencies = list(Counter(nums).values())

        m = len(quantity)
        full_mask = (1 << m) - 1

        subset_sum = [0] * (1 << m)

        for mask in range(1 << m):
            total = 0

            for i in range(m):
                if mask & (1 << i):
                    total += quantity[i]

            subset_sum[mask] = total

        dp = [False] * (1 << m)
        dp[0] = True

        for count in frequencies:
            next_dp = dp[:]

            for mask in range(1 << m):
                if not dp[mask]:
                    continue

                remaining = full_mask ^ mask
                submask = remaining

                while submask:
                    if subset_sum[submask] <= count:
                        next_dp[mask | submask] = True

                    submask = (submask - 1) & remaining

            dp = next_dp

        return dp[full_mask]

The implementation begins by converting nums into frequency counts using Counter. Since customers only care about receiving equal numbers, the actual values are irrelevant.

The subset_sum array precomputes the total demand for every customer subset. This avoids recomputing sums repeatedly during DP transitions.

The DP array stores which customer subsets are currently satisfiable.

For each frequency bucket, we iterate through every reachable state and attempt to assign additional unsatisfied customer subsets.

The subset enumeration trick:

submask = (submask - 1) & remaining

efficiently iterates through all subsets of remaining.

Finally, if the full customer mask becomes reachable, all customers can be satisfied.

Go Solution

package main

func canDistribute(nums []int, quantity []int) bool {
	freqMap := make(map[int]int)

	for _, num := range nums {
		freqMap[num]++
	}

	frequencies := []int{}

	for _, count := range freqMap {
		frequencies = append(frequencies, count)
	}

	m := len(quantity)
	fullMask := (1 << m) - 1

	subsetSum := make([]int, 1<<m)

	for mask := 0; mask < (1 << m); mask++ {
		total := 0

		for i := 0; i < m; i++ {
			if mask&(1<<i) != 0 {
				total += quantity[i]
			}
		}

		subsetSum[mask] = total
	}

	dp := make([]bool, 1<<m)
	dp[0] = true

	for _, count := range frequencies {
		nextDP := make([]bool, 1<<m)
		copy(nextDP, dp)

		for mask := 0; mask < (1 << m); mask++ {
			if !dp[mask] {
				continue
			}

			remaining := fullMask ^ mask
			submask := remaining

			for submask > 0 {
				if subsetSum[submask] <= count {
					nextDP[mask|submask] = true
				}

				submask = (submask - 1) & remaining
			}
		}

		dp = nextDP
	}

	return dp[fullMask]
}

The Go implementation follows the same logic as the Python version.

Instead of Counter, a standard map is used for frequency counting.

Slices are used for DP arrays and subset sums. Go does not have Python's convenient list copying syntax, so copy() is used to duplicate the DP state.

Integer overflow is not a concern because all values remain comfortably within Go's int range.

Worked Examples

Example 1

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

Step 1: Frequencies

Value Count
1 1
2 1
3 1
4 1

Frequencies:

[1,1,1,1]

Step 2: Subset Sums

Mask Customers Sum
0 {} 0
1 {0} 2

Step 3: DP

Initial:

Mask Reachable
0 True
1 False

Each frequency is 1, but customer needs 2.

No transition succeeds.

Final:

dp[1] = False

Answer:

False

Example 2

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

Frequencies

[1,1,2]

Subset Sum

Mask Sum
0 0
1 2

DP Transition

When processing frequency 2:

subset_sum[1] = 2 <= 2

So:

dp[1] = True

Answer:

True

Example 3

nums = [1,1,2,2]
quantity = [2,2]

Frequencies

[2,2]

Subset Sums

Mask Customers Sum
00 {} 0
01 {0} 2
10 {1} 2
11 {0,1} 4

First Frequency

Using first 2:

dp[01] = True
dp[10] = True

Second Frequency

From 01, assign customer 1:

dp[11] = True

Answer:

True

Complexity Analysis

Measure Complexity Explanation
Time O(k * 3^m) Each frequency processes all masks and their submasks
Space O(2^m) DP and subset sum arrays

Here:

  • k is the number of unique integers in nums
  • m is the number of customers

The subset enumeration technique causes the total number of (mask, submask) pairs to become 3^m, which is feasible because m <= 10.

The memory usage remains small because only arrays of size 2^m are stored.

Test Cases

from typing import List

s = Solution()

assert s.canDistribute([1,2,3,4], [2]) == False
# Single customer cannot receive two equal numbers

assert s.canDistribute([1,2,3,3], [2]) == True
# One value appears twice

assert s.canDistribute([1,1,2,2], [2,2]) == True
# Two customers matched perfectly

assert s.canDistribute([1,1,1,1], [2,2]) == True
# Same value satisfies multiple customers

assert s.canDistribute([1,1,1], [2,2]) == False
# Total demand exceeds supply

assert s.canDistribute([1,1,1,2,2,2], [3,3]) == True
# Two exact large groups

assert s.canDistribute([1,1,1,1,2], [3,2]) == False
# One customer cannot be satisfied

assert s.canDistribute([1], [1]) == True
# Smallest valid input

assert s.canDistribute([1,1,1,1,1], [1,1,1,1,1]) == True
# Many small customers using same value

assert s.canDistribute([1,2,2,3,3,3], [1,2,3]) == True
# Multiple different frequency assignments

assert s.canDistribute([1,1,2,2,3,3], [2,2,2]) == True
# Every frequency used exactly once

assert s.canDistribute([1,1,1,2,2], [4,1]) == False
# Largest customer request impossible

Test Summary

Test Why
[1,2,3,4], [2] No repeated values available
[1,2,3,3], [2] Single valid repeated group
[1,1,2,2], [2,2] Multiple customers
[1,1,1,1], [2,2] Same value split across customers
[1,1,1], [2,2] Insufficient total supply
[1,1,1,2,2,2], [3,3] Exact partitioning
[1,1,1,1,2], [3,2] One request impossible
[1], [1] Minimum size case
[1,1,1,1,1], [1,1,1,1,1] Many small allocations
[1,2,2,3,3,3], [1,2,3] Mixed frequency sizes
[1,1,2,2,3,3], [2,2,2] All frequencies consumed
[1,1,1,2,2], [4,1] Largest request exceeds frequency

Edge Cases

One important edge case occurs when a customer requests more items than any frequency bucket contains. For example:

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

No value appears three times, so the answer must be false. A naive implementation might incorrectly combine different values, but the DP solution correctly prevents this because each subset assignment is checked against a single frequency count.

Another tricky edge case is when multiple customers share the same value. For example:

nums = [1,1,1,1]
quantity = [2,2]

Both customers can receive value 1. Some incorrect solutions assume one value can satisfy only one customer. The subset-based DP naturally handles splitting a frequency bucket across multiple customers.

A third important edge case occurs when many small customer requests exist:

nums = [1,1,1,1,1]
quantity = [1,1,1,1,1]

All customers can be satisfied using the same value. This stresses whether the algorithm correctly handles many subset combinations. Since the DP explores all customer subsets systematically, it correctly identifies the valid arrangement.

A final edge case involves unused numbers:

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

Only the two 1s matter. The remaining numbers are irrelevant. The implementation handles this naturally because frequencies that are not useful simply do not contribute successful DP transitions.