LeetCode 1481. Least Number of Unique Integers after K Removals Solution in Java, C++, Python & More | Explanation + Code

Description

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

 

Example 1:

Input: arr = [5,5,4], k = 1

Output: 1

Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3

Output: 2

Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

 

Constraints:

<li><code>1 &lt;= arr.length&nbsp;&lt;= 10^5</code></li>

<li><code>1 &lt;= arr[i] &lt;= 10^9</code></li>

<li><code>0 &lt;= k&nbsp;&lt;= arr.length</code></li>

Solutions

Solution 1: Hash Table + Sorting

We use the hash table cnt to count the number of times each integer in the array arr appears, and then sort the values in cnt in ascending order, and record them in the array nums.

Next, we traverse the array nums. For the current value that we traverse to nums[i], we subtract k by nums[i]. If k \lt 0, it means that we have removed k elements, and the minimum number of different integers in the array is the length of nums minus the index i that we traverse to at the current time. Return directly.

If we traverse to the end, it means that we have removed all the elements, and the minimum number of different integers in the array is 0.

The time complexity is O(n × log n), and the space complexity is O(n), where n is the length of the array arr.

PythonJavaC++GoTypeScript

class Solution: def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int: cnt = Counter(arr) for i, v in enumerate(sorted(cnt.values())): k -= v if k < 0: return len(cnt) - i return 0(code-box)

class Solution { public int findLeastNumOfUniqueInts(int[] arr, int k) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : arr) { cnt.merge(x, 1, Integer::sum); } List<Integer> nums = new ArrayList<>(cnt.values()); Collections.sort(nums); for (int i = 0, m = nums.size(); i < m; ++i) { k -= nums.get(i); if (k < 0) { return m - i; } } return 0; } }(code-box)

class Solution { public: int findLeastNumOfUniqueInts(vector<int>& arr, int k) { unordered_map<int, int> cnt; for (int& x : arr) { ++cnt[x]; } vector<int> nums; for (auto& [_, c] : cnt) { nums.push_back(c); } sort(nums.begin(), nums.end()); for (int i = 0, m = nums.size(); i < m; ++i) { k -= nums[i]; if (k < 0) { return m - i; } } return 0; } };(code-box)

func findLeastNumOfUniqueInts(arr []int, k int) int { cnt := map[int]int{} for _, x := range arr { cnt[x]++ } nums := make([]int, 0, len(cnt)) for _, v := range cnt { nums = append(nums, v) } sort.Ints(nums) for i, v := range nums { k -= v if k < 0 { return len(nums) - i } } return 0 }(code-box)

function findLeastNumOfUniqueInts(arr: number[], k: number): number { const cnt: Map<number, number> = new Map(); for (const x of arr) { cnt.set(x, (cnt.get(x) ?? 0) + 1); } const nums = [...cnt.values()].sort((a, b) => a - b); for (let i = 0; i < nums.length; ++i) { k -= nums[i]; if (k < 0) { return nums.length - i; } } return 0; }(code-box)