We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Distribute Repeating Integers

Number: 1758

Difficulty: Hard

Paid? No

Companies: Amazon, Google

Problem Description

Given an integer array nums (with at most 50 unique values) and an array quantity, where quantity[i] represents how many items the iᵗʰ customer needs, determine if it is possible to assign exactly quantity[i] identical integers from nums (each customer gets items of the same value) in such a way that every customer is satisfied.

Key Insights

  • Count the frequency of each unique integer in nums.
  • There are at most 50 unique integers, reducing the search space.
  • The assignment to each customer can be mapped to a bitmask since there are m (m ≤ 10) customers.
  • Use recursion/backtracking with bitmask DP by trying to assign a subset (of customers) to each frequency bucket if the total quantity required by that subset is less than or equal to the available frequency.
  • Precompute the sum of quantities for every subset of customers to speed up the check.

Space and Time Complexity

Time Complexity: O(unique * 2^m * 2^m) in worst-case given m customers and up to 50 unique numbers. Space Complexity: O(2^m) for memoization and O(2^m) additional space for subset sum mapping.

Solution

The solution uses a recursive backtracking strategy with dynamic programming (memoization) over the state represented by a bitmask (where each bit indicates if a customer’s order is still pending). We first compute frequency counts of each unique number available in nums. For all subsets of customers (since m ≤ 10, 2^m possibilities), precompute the sum of their order quantities. Then, for each frequency bucket, iterate over all non-empty subsets of remaining customers. If a subset’s total quantities are ≤ frequency, we try to “assign” this frequency group to satisfy these customers and recursively check if the remaining groups can fulfill the rest. Memoization caches results for states defined by the bitmask of unsatisfied customers.

Important structures & algorithms:

  • Hash Map (or Counter) to store frequencies.
  • Bitmask DP: Each state is a bitmask representing which customers orders have not been fulfilled.
  • Precomputation: For 2^(#customers) possible subsets, calculate the sum of required quantities.
  • Recursion with memoization to try various assignments.

Code Solutions

from collections import Counter
from functools import lru_cache

def canDistribute(nums, quantity):
    # Frequency count for unique numbers in nums
    freq = list(Counter(nums).values())
    n_group = len(freq)
    m = len(quantity)
    
    # Precompute sums for every subset of customers based on their order quantities.
    subset_sum = {}
    for mask in range(1 << m):
        total = 0
        for j in range(m):
            if mask & (1 << j):
                total += quantity[j]
        subset_sum[mask] = total

    # dp(pos, mask) returns True if from frequency groups starting at pos,
    # we can satisfy the customers indicated by mask (mask bit 1 = unsatisfied)
    @lru_cache(maxsize=None)
    def dp(pos, mask):
        # if all orders are satisfied
        if mask == 0:
            return True
        # if no more frequency groups available but orders remain:
        if pos == n_group:
            return False
        
        # Option1: Skip current frequency group
        if dp(pos + 1, mask):
            return True

        # Option2: try to satisfy some subset of remaining customers using current frequency freq[pos]
        # Iterate over all possible subsets of mask
        sub = mask
        while sub:
            # if current frequency is enough to satisfy this subset
            if subset_sum[sub] <= freq[pos]:
                # then try to satisfy the remaining customers
                if dp(pos + 1, mask ^ sub):
                    return True
            sub = (sub - 1) & mask  # move to next submask
        
        return False

    return dp(0, (1 << m) - 1)

# Example usage:
#print(canDistribute([1,2,3,3], [2]))  # Output: True
← Back to All Questions