# LeetCode: Reduce Array Size to The Half Solution

Hash table, sort by occurences then greedily remove

## Approach

Steps:

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

## Implementation

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**2 * @param {number[]} arr3 * @return {number}4 */5var minSetSize = function (arr) {6  const n = arr.length7
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 - occurrenceB15  )16
17  let i = n18  let setRemovedLength = 019
20  while (i > Math.floor(n / 2)) {21    i -= pairsSortedByOccurencesDesc.pop()[1]22    setRemovedLength++23  }24
25  return setRemovedLength26}```

## References

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

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

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

leetcode

hash table

sorting

greedy

## Next Post

LeetCode: Maximum Length of Repeated Subarray

Jul 8, 2021

Memoized recursion, somewhat similar to "Longest common subsequence"

Search Posts