1481. Least Number of Unique Integers after K Removal - Explanation

Description

Remove exactly k elements from arr. Return the smallest number of distinct integer values that can remain. Removing an element removes only that occurrence, and the removed positions do not need to be consecutive.

Example 1:

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

Output: 1

Explanation: Remove the single occurrences of 2 and 3. Only the value 1 remains, so the answer is 1.

Example 2:

Input: arr = [7,7,8]
k = 0

Output: 2

Explanation: No elements may be removed. The remaining distinct values are 7 and 8, giving 2.

Example 3:

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

Output: 0

Explanation: Remove both elements. The empty array contains zero distinct values.

Constraints:

1 <= arr.length <= 100000
1 <= arr[i] <= 1000000000
0 <= k <= arr.length

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Maps - Counting element frequencies efficiently using key-value data structures
Sorting - Understanding how to sort arrays and the time complexity implications
Greedy Algorithms - Making locally optimal choices (removing least frequent elements first) to achieve a global optimum
Heaps/Priority Queues - For the min-heap approach, understanding how to efficiently extract minimum values

1. Sorting

Intuition

To minimize the number of unique integers after removing k elements, we should prioritize removing integers that appear least frequently. By eliminating all occurrences of the rarest integers first, we reduce the unique count most efficiently. Sorting frequencies in ascending order lets us greedily remove elements starting from the smallest frequency.

Algorithm

Count the frequency of each integer using a hash map.
Extract the frequency values and sort them in ascending order.
Iterate through the sorted frequencies:
- If k is large enough to remove all occurrences of this integer, subtract the frequency from k and decrease the unique count.
- Otherwise, we cannot fully remove this integer, so return the remaining unique count.
If all integers can be removed, return 0.

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq = sorted(Counter(arr).values())
        n = len(freq)
        for i in range(n):
            if k >= freq[i]:
                k -= freq[i]
            else:
                return n - i
        return 0

public class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        List<Integer> freq = new ArrayList<>(freqMap.values());
        Collections.sort(freq);

        int n = freq.size();
        for (int i = 0; i < n; i++) {
            if (k >= freq.get(i)) {
                k -= freq.get(i);
            } else {
                return n - i;
            }
        }
        return 0;
    }
}

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> freqMap;
        for (int num : arr) {
            freqMap[num]++;
        }

        vector<int> freq;
        for (auto& [_, count] : freqMap) {
            freq.push_back(count);
        }

        sort(freq.begin(), freq.end());

        int n = freq.size();
        for (int i = 0; i < n; i++) {
            if (k >= freq[i]) {
                k -= freq[i];
            } else {
                return n - i;
            }
        }
        return 0;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @param {number} k
     * @return {number}
     */
    findLeastNumOfUniqueInts(arr, k) {
        let freqMap = new Map();
        for (let num of arr) {
            freqMap.set(num, (freqMap.get(num) || 0) + 1);
        }

        let freq = Array.from(freqMap.values()).sort((a, b) => a - b);

        let n = freq.length;
        for (let i = 0; i < n; i++) {
            if (k >= freq[i]) {
                k -= freq[i];
            } else {
                return n - i;
            }
        }
        return 0;
    }
}

public class Solution {
    public int FindLeastNumOfUniqueInts(int[] arr, int k) {
        Dictionary<int, int> freqMap = new Dictionary<int, int>();
        foreach (int num in arr) {
            if (!freqMap.ContainsKey(num)) freqMap[num] = 0;
            freqMap[num]++;
        }

        List<int> freq = new List<int>(freqMap.Values);
        freq.Sort();

        int n = freq.Count;
        for (int i = 0; i < n; i++) {
            if (k >= freq[i]) {
                k -= freq[i];
            } else {
                return n - i;
            }
        }
        return 0;
    }
}

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

    freq := make([]int, 0, len(freqMap))
    for _, count := range freqMap {
        freq = append(freq, count)
    }

    sort.Ints(freq)

    n := len(freq)
    for i := 0; i < n; i++ {
        if k >= freq[i] {
            k -= freq[i]
        } else {
            return n - i
        }
    }
    return 0
}

class Solution {
    fun findLeastNumOfUniqueInts(arr: IntArray, k: Int): Int {
        var remaining = k
        val freqMap = HashMap<Int, Int>()
        for (num in arr) {
            freqMap[num] = freqMap.getOrDefault(num, 0) + 1
        }

        val freq = freqMap.values.sorted()

        val n = freq.size
        for (i in 0 until n) {
            if (remaining >= freq[i]) {
                remaining -= freq[i]
            } else {
                return n - i
            }
        }
        return 0
    }
}

class Solution {
    func findLeastNumOfUniqueInts(_ arr: [Int], _ k: Int) -> Int {
        var k = k
        var freqMap = [Int: Int]()
        for num in arr {
            freqMap[num, default: 0] += 1
        }

        let freq = freqMap.values.sorted()

        let n = freq.count
        for i in 0..<n {
            if k >= freq[i] {
                k -= freq[i]
            } else {
                return n - i
            }
        }
        return 0
    }
}

impl Solution {
    pub fn find_least_num_of_unique_ints(arr: Vec<i32>, k: i32) -> i32 {
        let mut freq_map = HashMap::new();
        for &num in &arr {
            *freq_map.entry(num).or_insert(0) += 1;
        }

        let mut freq: Vec<i32> = freq_map.values().cloned().collect();
        freq.sort();

        let mut k = k;
        let n = freq.len();
        for i in 0..n {
            if k >= freq[i] {
                k -= freq[i];
            } else {
                return (n - i) as i32;
            }
        }
        0
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Min-Heap

Intuition

A min-heap naturally gives us access to the smallest frequency first. Instead of sorting all frequencies upfront, we can repeatedly extract the minimum frequency and try to remove that integer. This approach works similarly to sorting but uses a heap data structure for extraction.

Algorithm

Build a frequency map of all integers.
Insert all frequency values into a min-heap.
While k > 0 and the heap is not empty:
- Pop the smallest frequency.
- If k can cover this frequency, subtract it from k and decrement the result count.
- Otherwise, stop (we cannot fully remove this integer).
Return the remaining unique count.

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq = Counter(arr)
        heap = list(freq.values())
        heapq.heapify(heap)

        res = len(heap)
        while k > 0 and heap:
            f = heapq.heappop(heap)
            if k >= f:
                k -= f
                res -= 1
        return res

public class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Integer> minHeap = new PriorityQueue<>(freqMap.values());

        int res = minHeap.size();
        while (k > 0 && !minHeap.isEmpty()) {
            int f = minHeap.poll();
            if (k >= f) {
                k -= f;
                res--;
            }
        }
        return res;
    }
}

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> freqMap;
        for (int num : arr) {
            freqMap[num]++;
        }

        priority_queue<int, vector<int>, greater<int>> minHeap;
        for (auto& [_, count] : freqMap) {
            minHeap.push(count);
        }

        int res = minHeap.size();
        while (k > 0 && !minHeap.empty()) {
            int f = minHeap.top();
            minHeap.pop();
            if (k >= f) {
                k -= f;
                res--;
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @param {number} k
     * @return {number}
     */
    findLeastNumOfUniqueInts(arr, k) {
        let freqMap = new Map();
        for (let num of arr) {
            freqMap.set(num, (freqMap.get(num) || 0) + 1);
        }

        const minHeap = MinPriorityQueue.fromArray([...freqMap.values()]);

        let res = minHeap.size();
        while (k > 0 && !minHeap.isEmpty()) {
            let f = minHeap.pop();
            if (k >= f) {
                k -= f;
                res--;
            }
        }
        return res;
    }
}

public class Solution {
    public int FindLeastNumOfUniqueInts(int[] arr, int k) {
        Dictionary<int, int> freqMap = new Dictionary<int, int>();
        foreach (int num in arr) {
            if (!freqMap.ContainsKey(num)) freqMap[num] = 0;
            freqMap[num]++;
        }

        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();
        foreach (int f in freqMap.Values) {
            minHeap.Enqueue(f, f);
        }

        int res = minHeap.Count;
        while (k > 0 && minHeap.Count > 0) {
            int f = minHeap.Dequeue();
            if (k >= f) {
                k -= f;
                res--;
            }
        }
        return res;
    }
}

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

    minHeap := &IntHeap{}
    heap.Init(minHeap)
    for _, count := range freqMap {
        heap.Push(minHeap, count)
    }

    res := minHeap.Len()
    for k > 0 && minHeap.Len() > 0 {
        f := heap.Pop(minHeap).(int)
        if k >= f {
            k -= f
            res--
        }
    }
    return res
}

type IntHeap []int

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

class Solution {
    fun findLeastNumOfUniqueInts(arr: IntArray, k: Int): Int {
        var remaining = k
        val freqMap = HashMap<Int, Int>()
        for (num in arr) {
            freqMap[num] = freqMap.getOrDefault(num, 0) + 1
        }

        val minHeap = PriorityQueue<Int>()
        for (f in freqMap.values) {
            minHeap.offer(f)
        }

        var res = minHeap.size
        while (remaining > 0 && minHeap.isNotEmpty()) {
            val f = minHeap.poll()
            if (remaining >= f) {
                remaining -= f
                res--
            }
        }
        return res
    }
}

class Solution {
    func findLeastNumOfUniqueInts(_ arr: [Int], _ k: Int) -> Int {
        var k = k
        var freqMap = [Int: Int]()
        for num in arr {
            freqMap[num, default: 0] += 1
        }

        var minHeap = Heap<Int>()
        for f in freqMap.values {
            minHeap.insert(f)
        }

        var res = minHeap.count
        while k > 0 && !minHeap.isEmpty {
            let f = minHeap.removeMin()
            if k >= f {
                k -= f
                res -= 1
            }
        }
        return res
    }
}

impl Solution {
    pub fn find_least_num_of_unique_ints(arr: Vec<i32>, k: i32) -> i32 {
        let mut freq_map = HashMap::new();
        for &num in &arr {
            *freq_map.entry(num).or_insert(0) += 1;
        }

        let mut min_heap = BinaryHeap::new();
        for &count in freq_map.values() {
            min_heap.push(Reverse(count));
        }

        let mut k = k;
        let mut res = min_heap.len() as i32;
        while k > 0 && !min_heap.is_empty() {
            let Reverse(f) = min_heap.pop().unwrap();
            if k >= f {
                k -= f;
                res -= 1;
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Bucket Sort

Intuition

Since frequencies are bounded by the array length, we can use bucket sort to avoid comparison-based sorting. We create buckets where bucket f contains the count of integers with frequency f. Then we iterate through buckets from frequency 1 upward, removing as many complete integers as possible at each frequency level.

Algorithm

Build a frequency map of all integers.
Create a frequency list (bucket array) where freqList[f] counts how many integers have frequency f.
Iterate f from 1 to the array length:
- Calculate how many integers with frequency f can be fully removed given the remaining k.
- Subtract the cost from k and reduce the result count.
- If k cannot remove all integers at this frequency, compute partial removal and break.
Return the remaining unique count.

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq = Counter(arr)
        freq_list = [0] * (len(arr) + 1)

        for n, f in freq.items():
            freq_list[f] += 1

        res = len(freq)
        for f in range(1, len(freq_list)):
            remove = freq_list[f]
            if k >= f * remove:
                k -= f * remove
                res -= remove
            else:
                remove = k // f
                res -= remove
                break
        return res

public class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        int[] freqList = new int[arr.length + 1];
        for (int f : freqMap.values()) {
            freqList[f]++;
        }

        int res = freqMap.size();
        for (int f = 1; f < freqList.length; f++) {
            int remove = freqList[f];
            if (k >= f * remove) {
                k -= f * remove;
                res -= remove;
            } else {
                remove = k / f;
                res -= remove;
                break;
            }
        }
        return res;
    }
}

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> freqMap;
        for (int num : arr) {
            freqMap[num]++;
        }

        vector<int> freqList(arr.size() + 1, 0);
        for (auto& [_, f] : freqMap) {
            freqList[f]++;
        }

        int res = freqMap.size();
        for (int f = 1; f < freqList.size(); f++) {
            int remove = freqList[f];
            if (k >= f * remove) {
                k -= f * remove;
                res -= remove;
            } else {
                remove = k / f;
                res -= remove;
                break;
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @param {number} k
     * @return {number}
     */
    findLeastNumOfUniqueInts(arr, k) {
        let freqMap = new Map();
        for (let num of arr) {
            freqMap.set(num, (freqMap.get(num) || 0) + 1);
        }

        let freqList = new Array(arr.length + 1).fill(0);
        for (let f of freqMap.values()) {
            freqList[f]++;
        }

        let res = freqMap.size;
        for (let f = 1; f < freqList.length; f++) {
            let remove = freqList[f];
            if (k >= f * remove) {
                k -= f * remove;
                res -= remove;
            } else {
                remove = Math.floor(k / f);
                res -= remove;
                break;
            }
        }
        return res;
    }
}

public class Solution {
    public int FindLeastNumOfUniqueInts(int[] arr, int k) {
        Dictionary<int, int> freqMap = new Dictionary<int, int>();
        foreach (int num in arr) {
            if (!freqMap.ContainsKey(num)) freqMap[num] = 0;
            freqMap[num]++;
        }

        int[] freqList = new int[arr.Length + 1];
        foreach (int f in freqMap.Values) {
            freqList[f]++;
        }

        int res = freqMap.Count;
        for (int f = 1; f < freqList.Length; f++) {
            int remove = freqList[f];
            if (k >= f * remove) {
                k -= f * remove;
                res -= remove;
            } else {
                remove = k / f;
                res -= remove;
                break;
            }
        }
        return res;
    }
}

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

    freqList := make([]int, len(arr)+1)
    for _, f := range freqMap {
        freqList[f]++
    }

    res := len(freqMap)
    for f := 1; f < len(freqList); f++ {
        remove := freqList[f]
        if k >= f*remove {
            k -= f * remove
            res -= remove
        } else {
            remove = k / f
            res -= remove
            break
        }
    }
    return res
}

class Solution {
    fun findLeastNumOfUniqueInts(arr: IntArray, k: Int): Int {
        var remaining = k
        val freqMap = HashMap<Int, Int>()
        for (num in arr) {
            freqMap[num] = freqMap.getOrDefault(num, 0) + 1
        }

        val freqList = IntArray(arr.size + 1)
        for (f in freqMap.values) {
            freqList[f]++
        }

        var res = freqMap.size
        for (f in 1 until freqList.size) {
            var remove = freqList[f]
            if (remaining >= f * remove) {
                remaining -= f * remove
                res -= remove
            } else {
                remove = remaining / f
                res -= remove
                break
            }
        }
        return res
    }
}

class Solution {
    func findLeastNumOfUniqueInts(_ arr: [Int], _ k: Int) -> Int {
        var k = k
        var freqMap = [Int: Int]()
        for num in arr {
            freqMap[num, default: 0] += 1
        }

        var freqList = [Int](repeating: 0, count: arr.count + 1)
        for f in freqMap.values {
            freqList[f] += 1
        }

        var res = freqMap.count
        for f in 1..<freqList.count {
            var remove = freqList[f]
            if k >= f * remove {
                k -= f * remove
                res -= remove
            } else {
                remove = k / f
                res -= remove
                break
            }
        }
        return res
    }
}

impl Solution {
    pub fn find_least_num_of_unique_ints(arr: Vec<i32>, k: i32) -> i32 {
        let mut freq_map = HashMap::new();
        for &num in &arr {
            *freq_map.entry(num).or_insert(0i32) += 1;
        }

        let mut freq_list = vec![0i32; arr.len() + 1];
        for &f in freq_map.values() {
            freq_list[f as usize] += 1;
        }

        let mut k = k;
        let mut res = freq_map.len() as i32;
        for f in 1..freq_list.len() {
            let f = f as i32;
            let mut remove = freq_list[f as usize];
            if k >= f * remove {
                k -= f * remove;
                res -= remove;
            } else {
                remove = k / f;
                res -= remove;
                break;
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Removing High-Frequency Elements First

The greedy strategy requires removing elements with the lowest frequency first to maximize the reduction in unique count. Removing high-frequency elements wastes removals since you need more deletions to eliminate a single unique integer. Always sort frequencies in ascending order.

Counting Unique Integers Incorrectly

A subtle bug is decrementing the unique count even when you cannot fully remove all occurrences of an integer. If k is less than the current frequency, you cannot eliminate that unique integer, so the count should not decrease. Only reduce the unique count when all occurrences are removed.

Forgetting Partial Removal Logic

When k cannot fully cover the current frequency but can partially cover it, some implementations incorrectly skip this case entirely. While partial removal does not reduce the unique count, you still need to account for it when moving to the next frequency bucket in bucket sort approaches.