How to check if two given sets are disjoint?

Difficulty Level Easy
Frequently asked in Factset Hike Kuliza Nagarro Opera Snapdeal
Array Binary Search Hash Larsen & Toubro Searching SortingViews 2292

The problem “How to check if two given sets are disjoint?” states that suppose you are given two sets in the form of array say set1[] and set2[]. Your task is to find out whether the two sets are Disjoint Sets or not.

Example

inputSet1[] = {1, 15, 8, 9, 6}
inputSet2[] = {2, 4, 19, 3}
These are Disjoint Sets

Explanation

Since there are no common elements in both the set so they are disjoint sets

inputSet1[] = {2, 1, 6, 9, 7}
inputSet2[] = {2, 4, 19, 3}
These are not Disjoint Sets

Explanation

Here 2 is a common element in both the set so they are not disjoint sets.

Algorithm

  1. Declare a HashSet.
  2. Insert all the elements of set1 into HashSet.
  3. Traverse all the elements of set2[] and check whether if HashSet contains any of the elements of set2[].
    1. If it contains, then returns false.
  4. Return true.

Explanation

We have given a problem statement that asks to find out whether the two given sets are disjoint sets or not. Both of the sets are represented as an array. We will use a HashSet and inherit the properties of HashSet. A HashSet doesn’t allow to store duplicate values.

Declare a  Boolean function which simply returns either true or false. We will pass two arrays to that Boolean function and the first thing it will do is storing the value of set1[]  to HashSet and after storing each value in it of set1[] it will check whether HashSet contains any of the elements of set2[]. It returns false, that means set1[] and set2[] have a common element. Thus these are not disjoint sets and returns false.

Let us consider an example here, we will take two sets and perform our algorithm on it:

Set1[] = {2, 1, 6, 9, 7}

Set2[] = {4, 2, 19, 3}

HashSet myset;

For storing the value of set1 into HashSet, we will traverse each of the elements of set1 and insert all of the elements into “myset”.

For set1[]

i=0, myset = {2}

i=1, myset = {2, 1}

i=2, myset = {2, 1, 6}

i=3, myset = {2, 1, 6, 9}

i=4, myset = {2, 1, 6, 9, 7}

We got our Hashset. We will look forward to finding an element of set2[] (if any) in a HashSet. Traversing the set2 []={4, 2, 19, 3};

j=0, set2[ j ]=4

myset will not find 4 in HashSet

j=0, set2[ j ]=2

myset will find 2 in HashSet, so it will returns false and our output prints “These are not Disjoint Sets”. In case if any if any of the elements of set2 [] doesn’t match in myset then it will come out of the loop and return true.

C++ code to check if two sets are disjoint

#include<set>
#include<iostream>

using namespace std;

bool areDisjointSets(int set1[], int set2[],int n1,int n2)
{
    set<int> myset;

    for (int i = 0; i < n1; i++)
    {
        myset.insert(set1[i]);
    }
    for (int j = 0; j < n2; j++)
    {
        if (myset.find(set2[j]) != myset.end())
            return false;
    }
    return true;
}
int main()
{
    int set1[] = {1, 15, 8, 9, 6};
    int set2[] = {2, 4, 19, 3};

    int n1 = sizeof(set1) / sizeof(set1[0]);
    int n2 = sizeof(set2) / sizeof(set2[0]);

    if (areDisjointSets(set1, set2, n1, n2))
        cout << "These are Disjoint Sets";
    else
        cout << "These are not Disjoint Sets";

    return 0;
}

These are Disjoint Sets

Java code to check if two sets are disjoint

import java.util.*;

class twoDisjointSets
{
    public static boolean areDisjointSets(int set1[], int set2[])
    {
        HashSet<Integer> myset = new HashSet<>();
        for (int i=0; i<set1.length; i++)
        {
            myset.add(set1[i]);
        }
        for (int j=0; j<set2.length; j++)
        {
            if (myset.contains(set2[j]))
            {
                return false;
            }
        }
        return true;
    }
    public static void main (String[] args)
    {
        int inputSet1[] = {1, 15, 8, 9, 6};
        int inputSet2[] = {2, 4, 19, 3};
        if (areDisjointSets(inputSet1, inputSet2))
            System.out.println("These are Disjoint Sets");
        else
            System.out.println("These are not Disjoint Sets");
    }
}

These are Disjoint Sets

Complexity Analysis

Time Complexity

O(m+n) where “m” and “n” are the number of elements in set1 and set2 respectively. First, we enter all elements of the first set into HashSet which contributes for O(N) time complexity. Then we traverse the elements of the second set.

Space Complexity

O(m) where “m”  is the size of the first set. We can also optimize the solution to store the array which has a minimum number of elements.

Translate »