Least Number of Unique Integers after K Removals

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 = [4,3,1,1,3,3,2], k = 3
Output: 2

Approach

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

public class LeastNumUnique {
    public static void main(String[] args) {
        int[] arr =  {4, 3, 1, 1, 3, 3, 2};
        int k = 3;
        System.out.println(findLeastNumOfUniqueInts(arr, k));
    }

    static int findLeastNumOfUniqueInts(int[] arr, int k) {
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
        for (int i : arr)
            mp.put(i, mp.getOrDefault(i, 0) + 1);

        List<int[]> v = new ArrayList<int[]>();
        for (int key : mp.keySet())
            v.add(new int[] { mp.get(key), key });
        Collections.sort(v, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int i = 0;
        for (i = 0; i < v.size(); i++) {

            if (k > 0) {
                if (v.get(i)[0] <= k)
                    k -= v.get(i)[0];
                else
                    break;
            } else
                break;
        }
        return v.size() - i;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int findLeastNumOfUniqueInts(vector<int> &arr, int k)
{
    unordered_map<int, int> mp;
    for (int i = 0; i < arr.size(); i++)
        mp[arr[i]]++;
    vector<pair<int, int>> v;
    for (auto it = mp.begin(); it != mp.end(); it++)
        v.push_back({it->second, it->first});
    sort(v.begin(), v.end());
    int i = 0;
    for (i = 0; i < v.size(); i++)
    {

        if (k > 0)
        {
            if (v[i].first <= k)
                k -= v[i].first;
            else
                break;
        }
        else
            break;
    }
    return v.size() - i;
}

int main()
{
    vector<int> arr = {4, 3, 1, 1, 3, 3, 2};
    int k = 3;
    cout << findLeastNumOfUniqueInts(arr, k);
    return 0;
}