Reduce Array Size to The Half Solution
Vartika Gupta
152
Hash TableInterview

C++| Simple & Clean Solution | Easy to Understand | Hashmap | Set

  • Count the frequency of each integer in the array and store it in hashmap.
  • Put all the values of hashmap into vector of pairs with first element of pair as value & second element of pair as key of map.
  • Start with an empty set, add to the set the integer with the maximum frequency.
  • Keep Adding the integer with the max frequency until you remove at least half of the integers.
class Solution {
public:
    int minSetSize(vector<int>& arr) {
        map<int,int>map;
        int n=arr.size();
        for(int i=0;i<n;i++){
            map[arr[i]]++;
        }
        vector<pair<int,int>>v;
        for(auto m:map){
            v.push_back({m.second,m.first});
        }
        sort(v.begin(),v.end());
        int v_size=v.size();
        set<int>s;
        int com=n;
        for(int i=v_size-1;i>=0;i--){
            if(com>(n/2)){
                s.insert(v[i].second);
                com=com-v[i].first;
            }
            else{
                break;
            }
        }
        return s.size();
        
    }
};

Happy Coding!!!

Comments (0)