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

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)

Comments

Loading comments...

Tags

leetcode

hash table

sorting

greedy

Next Post

LeetCode: Maximum Length of Repeated Subarray

Jul 8, 2021

Memoized recursion, somewhat similar to "Longest common subsequence"

Previous Post

HoningJS

Search Posts