LeetCode 1655: Distribute Repeating Integers

Explanation:

To solve this problem, we can use backtracking with memoization. We will try all possible distributions of integers to the customers and keep track of the remaining quantities for each customer.

1. Create a hashmap to count the frequency of each unique integer in the input array nums.
2. Define a backtracking function that takes the current index of the quantity array and the remaining quantities for each customer as parameters.
3. In the backtracking function:
   • If all customers are satisfied, return true.
   • Iterate through the remaining quantities for the current customer and try assigning different available values to satisfy the quantity.
   • Recursively call the backtracking function with updated remaining quantities after assigning the values.
4. Use memoization to avoid redundant calculations by storing the state of remaining quantities in a hashmap.
5. Return true if a valid distribution is found, false otherwise.

Time Complexity:

The time complexity of this approach is O(2^m * n), where n is the number of unique values in the input array nums and m is the number of customers.

Space Complexity:

The space complexity is O(n + m) for the hashmap storing frequency of unique values in nums and the recursive call stack.

:

class Solution {
    public boolean canDistribute(int[] nums, int[] quantity) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        return backtrack(freq, quantity, 0, new HashMap<>());
    }

    private boolean backtrack(Map<Integer, Integer> freq, int[] quantity, int idx, Map<String, Boolean> memo) {
        if (idx >= quantity.length) {
            return true;
        }
        StringBuilder sb = new StringBuilder();
        for (int count : freq.values()) {
            sb.append(count).append(",");
        }
        if (memo.containsKey(sb.toString())) {
            return memo.get(sb.toString());
        }

        boolean res = false;
        for (int key : freq.keySet()) {
            if (freq.get(key) >= quantity[idx]) {
                freq.put(key, freq.get(key) - quantity[idx]);
                res = res || backtrack(freq, quantity, idx + 1, memo);
                freq.put(key, freq.get(key) + quantity[idx]);
            }
        }

        memo.put(sb.toString(), res);
        return res;
    }
}