Minimum number of subsets with distinct elements

Problem Statement

Suppose you have an array of integers of size n. The problem statement asks to find out the minimum number of subsets with distinct elements, that is subsets that can be formed which contain all the different/distinct elements from the array.

Example

arr[] = {2,4,6,2,1,4,2}

3

Explanation: {1, 2, 4, 6}, {2, 4} and {2} can be the subsets.

arr[] = {2,5,6,7,5,4,2}

3

Explanation: {2, 5, 6, 7} and {2, 4} can be the two subsets.

Algorithm to find the minimum number of subsets with distinct elements

1. Declare a map and count and store the frequency of each element of the array into the map.
2. Set output to 0.
3. Traverse the map and find out the maximum between the output and each value of key in the map and store it into the output.
4. Return the value of output.

Explanation

We have given an integer array in which positive numbers are stored. We have asked to find out the count of minimum possible subsets that can be formed from the given array and has all distinct elements in the subset. For this we are going to use Hashing, Hashing provides an efficient solution in which we can achieve good time complexity instead of a naive approach.

We are going to declare a map, count, and store the frequencies of each element of an array. If we have a new entry in a map for some element we make a place for it and for the next time if the same element occurs we will just get that value and increase its frequency by 1. In C++, it itself picks up the element and then we just perform increment operation but in java, we to check for that element in particular. We are storing up the count of frequencies because we are going to find out the maximum frequency among all the elements and results in our answer.

We will set the output to 0, and then we will traverse the map in which we have stored the frequencies of each element. With this, we need not sort the array because with the map we have the elements inside it already sorted. We will pick up each element and get its frequency and compare it with the output. We need to find out the maximum of those two values, the output, and the frequency of picked elements. And that is the required answer to find minimum number of subsets with distinct elements.

Code to find the minimum number of subsets with distinct elements

C++ code

#include <iostream>
#include<unordered_map>

using namespace std;

int getMinSubset(int arr[], int n)
{
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++)
        mp[arr[i]]++;

    int output = 0;
    for (auto x : mp)
        output = max(output, x.second);

    return output;
}
int main()
{
    int arr[] = {2,4,6,2,1,4,2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMinSubset(arr, n);
    return 0;
}

3

Java Code

import java.util.HashMap;
import java.util.Map;

class MinimumSubsets
{
    public static int getMinSubset(int arr[], int n)
    {
        HashMap<Integer, Integer> mp = new HashMap<>();
        for (int i = 0; i < n; i++)
            mp.put(arr[i],mp.get(arr[i]) == null?1:mp.get(arr[i])+1);

        int output = 0;
        for (Map.Entry<Integer,Integer> entry : mp.entrySet())
            output = Math.max(output, entry.getValue());

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2,4,6,2,1,4,2};
        int n = arr.length;
        System.out.println( getMinSubset(arr, n));

    }
}

3

Complexity Analysis

Time Complexity

Here, we have used unordered_map or hash map which makes insertion, deletion, and updation in O(1). Thus, we have a linear complexity of O(n) where “n” is the number of elements in the array.

Space Complexity

Since we are storing key and value pairs, so at max, there will be n pairs that give us O(n) space complexity where “n” is the number of elements in the array. Thus we can say algorithm to find minimum number of subsets with distinct elements has linear space complexity solution.