LeetCode: Reduce Array Size to The Half Solution

Approach

Steps:

• Build hash map with key-value pairs of element-occurence
• Sort the pairs by occurence
• Greedily remove from the largest occurence

Implementation

1/**
2 * @param {number[]} arr
3 * @return {number}
4 */
5var minSetSize = function (arr) {
6  const n = arr.length
7
8  const occurrences = arr.reduce(
9    (acc, el) => acc.set(el, (acc.get(el) || 0) + 1),
10    new Map()
11  )
12
13  const pairsSortedByOccurencesDesc = [...occurrences.entries()].sort(
14    ([_, occurrenceA], [__, occurrenceB]) => occurrenceA - occurrenceB
15  )
16
17  let i = n
18  let setRemovedLength = 0
19
20  while (i > Math.floor(n / 2)) {
21    i -= pairsSortedByOccurencesDesc.pop()[1]
22    setRemovedLength++
23  }
24
25  return setRemovedLength
26}

References

Array.prototype.reduce() (MDN Web Docs)

Array.prototype.sort() (MDN Web Docs)

Map.prototype.entries() (MDN Web Docs)