Least Number of Unique Integers after K Removals - LeetCode Daily Challenge

Problem Statement

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.

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((e1, e2) -> e1.getValue() - e2.getValue());

        for(int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        minHeap.addAll(frequencyMap.entrySet());

        while(k > 0) {
            Map.Entry<Integer, Integer> entry = minHeap.poll();
            k -= entry.getValue();
        }
        
        return (k < 0) ? (minHeap.size() + 1) : minHeap.size();
    }
}

C++ Code

class Solution {
public:

    struct comparator {
        bool operator() (pair<int, int> &x, pair<int, int> &y) {
            return x.second > y.second;
        }
    };

    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> frequencyMap;
        priority_queue<pair<int, int>, vector<pair<int, int>>, comparator> minHeap;

        for (int num : arr) {
            frequencyMap[num]++;
        }

        for (auto& entry : frequencyMap) {
            minHeap.push(entry);
        }

        while (k > 0) {
            auto entry = minHeap.top();
            minHeap.pop();
            k -= entry.second;
        }

        return (k < 0) ? (minHeap.size() + 1) : minHeap.size();
    }
};

Python Code

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        frequency_map = dict()
        min_heap = []
        
        for num in arr:
            frequency_map[num] = frequency_map.get(num, 0) + 1

        for key, value in frequency_map.items():
            heappush(min_heap, (value, key))

        while k > 0:
            freq, _ = heapq.heappop(min_heap)
            k -= freq

        return len(min_heap) + (k < 0)

Javascript Code

var findLeastNumOfUniqueInts = function(arr, k) {
    const frequencyMap = new Map();
    arr.forEach(num => {
        frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
    });

    // using sorting instead of PriorityQueue
    const minHeap = [...frequencyMap.entries()].sort((a, b) => a[1] - b[1]);
    
    while (k > 0) {
        const [num, freq] = minHeap.shift();
        k -= freq;
    }
    
    return minHeap.length + (k < 0 ? 1 : 0);
};

Go Code

package main

import (
	"container/heap"
)

func findLeastNumOfUniqueInts(arr []int, k int) int {
	frequencyMap := make(map[int]int)
	for _, num := range arr {
		frequencyMap[num]++
	}

	minHeap := &minHeap{}
	heap.Init(minHeap)

	for num, freq := range frequencyMap {
		heap.Push(minHeap, [2]int{freq, num})
	}

	for k > 0 {
		entry := heap.Pop(minHeap).([2]int)
		k -= entry[0]
	}

	result := minHeap.Len()
    if k < 0 {
        result++
    }
    
    return result
}

type minHeap [][2]int

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i][0] < h[j][0] }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.([2]int)) }
func (h *minHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

Complexity Analysis

Time Complexity: O(N * logN)
Space Complexity: O(N)