Distribute Repeating Integers LeetCode solution in Java

1
class Solution {
2
  public boolean canDistribute(int[] nums, int[] quantity) {
3

4
    // Use a map to count the numbers, ex: nums:[5,7,4,7,4,7] -> {5:1, 7:3, 4:2}
5
    Map<Integer, Integer> freq = new HashMap<>();
6
    for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);
7

8
    // Turn values of the map into array, ex: {5:1, 7:3, 4:2} -> [1, 3, 2]
9
    int[] dist = new int[freq.size()];
10
    int idx = 0;
11
    for (int f : freq.values()) dist[idx++] = f;
12

13
    // Fullfill the quantities from the biggest quantity to the smallest.
14
    // If the bigger quantity can't be filled, the program will stop as early as possible.
15
    Arrays.sort(quantity);
16
    return rec(dist, quantity, quantity.length - 1);
17
  }
18

19
  // try to fullfill the j-th order quantity
20
  private boolean rec(int[] dist, int[] quantity, int j) {
21

22
    // stop condition. We've fulfilled all the order quantities.
23
    if (j == -1) return true;
24

25
    Set<Integer> used = new HashSet<>();
26
    for (int i = 0; i < dist.length; ++i) {
27

28
      // Use a set to make sure that
29
      //   we don't distribute from the same amount to this j-th order for more than once.
30
      // With this check, the program reduces from 97ms to 25 ms.
31
      if (dist[i] >= quantity[j] && used.add(dist[i])) {
32
        dist[i] -= quantity[j];
33
        if (rec(dist, quantity, j - 1)) return true;
34
        dist[i] += quantity[j];
35
      }
36
    }
37
    return false;
38
  }
39
}