Minimum Incompatibility LeetCode solution in JavaScript

1
////////////////////////////////////////////////////////////////////////////////////////////
2
////////////////////////////////////////////////////////////////////////////////////////////
3
////////////////////////////////////////////////////////////////////////////////////////////
4

5
var minimumIncompatibility = function (nums, k) {
6
  ////// FROM HERE TO
7
  if (nums.length === k) return 0;
8

9
  const maxInBucket = nums.length / k;
10
  const freqCount = {};
11
  for (const n of nums) {
12
    if (freqCount[n]) {
13
      if (freqCount[n] === k) {
14
        return -1;
15
      } else {
16
        freqCount[n]++;
17
      }
18
    } else {
19
      freqCount[n] = 1;
20
    }
21
  }
22
  /////// HERE is just saving time
23

24
  // create a cache (aka memo, dp, dynamic programming, momoization)
25
  const cache = {};
26
  // create a mask to know when all the indicies are used
27
  const allIndiciesUsedMask = 2 ** nums.length - 1;
28

29
  const dfs = (usedIndicesBitMask) => {
30
    // if we have used all the indicies then we return 0
31
    if (usedIndicesBitMask === allIndiciesUsedMask) {
32
      return 0;
33
    }
34
    // if we have seen this combination before, return the
35
    // result that was calculated before
36
    // otherwise do the hard work LOL
37
    if (cache[usedIndicesBitMask]) {
38
      return cache[usedIndicesBitMask];
39
    }
40

41
    // find all the indicies that are available to be used
42
    // skip duplicate values
43
    const valsToIndices = {};
44
    for (let i = 0; i < nums.length; i++) {
45
      const indexMask = 1 << i;
46
      if (usedIndicesBitMask & indexMask) continue;
47
      const value = nums[i];
48
      if (!valsToIndices.hasOwnProperty(value)) {
49
        valsToIndices[value] = i;
50
      }
51
    }
52
    const indicesAvailable = Object.values(valsToIndices);
53

54
    // this is hard to explain but it's basically calculating the minimum
55
    // cost while marking the indicies that are going to be used for each
56
    // combination
57
    let minIncompatibilityCost = Infinity;
58
    const combinations = createCombinations(indicesAvailable, maxInBucket);
59
    for (const indices of combinations) {
60
      let nextMask = usedIndicesBitMask;
61
      let minVal = Infinity;
62
      let maxVal = -Infinity;
63
      for (const index of indices) {
64
        minVal = Math.min(minVal, nums[index]);
65
        maxVal = Math.max(maxVal, nums[index]);
66
        nextMask = nextMask | (1 << index);
67
      }
68
      const incompatibilityCost = maxVal - minVal;
69
      minIncompatibilityCost = Math.min(
70
        minIncompatibilityCost,
71
        dfs(nextMask) + incompatibilityCost
72
      );
73
    }
74
    return (cache[usedIndicesBitMask] = minIncompatibilityCost);
75
  };
76
  return dfs(0);
77
};
78

79
function createCombinations(indices, len) {
80
  const combinations = [];
81

82
  if (indices.length < len) {
83
    return combinations;
84
  }
85

86
  const stack = [[[], 0]];
87
  while (stack.length > 0) {
88
    let [combi, i] = stack.pop();
89
    for (; i < indices.length; i++) {
90
      const combination = [...combi, indices[i]];
91
      if (combination.length === len) {
92
        combinations.push(combination);
93
      } else {
94
        stack.push([combination, i + 1]);
95
      }
96
    }
97
  }
98

99
  return combinations;
100
}