_1481. Least Number of Unique Integers after K Removals.md

1481. Least Number of Unique Integers after K Removals

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 15, 2024

Last updated : June 15, 2024

---

Related Topics : Array, Hash Table, Greedy, Sorting, Counting

Acceptance Rate : 63.17 %

---

Solutions

• m1481 v1.py
• m1481 v2-2.py
• m1481 v2.py

Python

m1481 v1.py

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = Counter(arr)

        # Sort so that lease frequent are at the end, groupped by their value
        arr.sort(reverse=True, key=lambda x: (cnt.get(x), x))

        for _ in range(k) :
            poppedVal = arr.pop()
            if cnt.get(poppedVal) == 1 :
                cnt.pop(poppedVal)
            else :
                cnt[poppedVal] = cnt.get(poppedVal) - 1
        
        return len(cnt)

m1481 v2-2.py

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = Counter(arr)

        # We don't care which values we pop, just that we do it greedily
        cntValues = sorted([freq for freq in cnt.values()], reverse=True)

        while k > 0 and cntValues[-1] <= k:
            k -= cntValues.pop()

        return len(cntValues)

m1481 v2.py

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = Counter(arr)

        # We don't care which values we pop, just that we do
        cntValues = sorted([freq for freq in cnt.values()], reverse=True)

        while k > 0 :
            if cntValues[-1] <= k :     # we can keep popping
                k -= cntValues.pop()
            else :                      # we can pop no longer
                break

        return len(cntValues)