Example
Input:
SetA[] = {1, 2, 3, 4, 5} & SetB[] = {6, 7, 8, 9, 1}
Output:
Not Disjoint
Reason: 1 is common in two sets.
Input:
SetA[] = { 1, 2, 3, 4 } & SetB[] = {5, 6, 7, 8}
Output:
Disjoint
Reason: The two sets have nothing in common.
Approach I ( Brute Force )
Algorithm / Steps

Create two variables: a boolean flag and an integer sum.

while i < size, traverse the array

While j<size, traverse the second array

If the iâ€™th element is present in the second array

Return false
 Return true
Time Complexity
O(N*N): Where â€˜Nâ€™ is the length of the array.
Reason: The worstcase scenario is when we are checking for each element in another array.
Auxiliary Space Complexity
O(1): Constant Space
Reason: No Additional space is required.
Approach II ( Hashing )
We are given two sets, presuming that both sets are already sorted, and we compare the elements in the two sets. If there is a match, the set is not disjoint; if there is no match, the set is disjoint.
Algorithm / Steps
Letâ€™s quickly walk through the algorithm for the Check If Two Given Sets Are Disjoint problem:

Make a hash table.

Go through the first set several times and add each element to the hash table.

Check to see if any elements are present in the hash table as you iterate over the second batch. Returns false if the element is present; else, disregard it.
 Return true if none of the second set's elements are found in the hash table.
Algorithm Walkthrough
 After creating a map weâ€™ll iterate through the array,
 And store each element in the map after checking whether the element is present on the map or not,
 If the element is present already on the map; return false.
Implementation in C++
Solution of the problem Check If Two Given Sets Are Disjoint in C++.
#include<bits/stdc++.h>
using namespace std;
bool checkDisjoint(vector<int> setA, vector<int> setB, int n1, int n2) {
/* Creates an empty hashset using set */
set<int> myset;
/* traverse the first set, then hash its components. */
for (int i = 0; i < n1; i++)
myset.insert(setA[i]);
/* Check the second set and determine whether any of its elements have already been hashed or not. */
for(int i = 0; i < n2; i++)
if (myset.find(setB[i]) != myset.end())
return false;
return true;
}
int main() {
vector<int> setA{1, 2, 3, 4, 5};
vector<int> setB{6, 7, 9, 5};
if (checkDisjoint(setA, setB, setA.size(), setB.size()))
cout << "Disjoint";
else
cout << "Not Disjoint";
}
Output:
Implementation in Java
Solution of the problem Check If Two Given Sets Are Disjoint in Java
import java.util.*;
public class HelloWorld {
static boolean checkDisjoint(int set1[], int set2[]) {
/* Creates an empty hashset using set */
HashSet<Integer> set = new HashSet<>();
/* traverse the first set, then hash its components. */
for (int i=0; i<set1.length; i++)
set.add(set1[i]);
/* Check the second set & determine whether any of its elements have already been hashed or not. */
for (int i=0; i<set2.length; i++)
if (set.contains(set2[i]))
return false;
return true;
}
public static void main (String[] args) {
int set1[] = {1, 2, 3, 4, 5};
int set2[] = {9, 6, 7, 8};
if (checkDisjoint(set1, set2))
System.out.println("A Disjoint Set");
else
System.out.println("Not Disjoint Set");
}
}
Output:
Implementation in Python
Solution of the problem Check If Two Given Sets Are Disjoint in Python.
def checkDisjoint(set1, set2, n1, n2):
# Creates an empty hashset
myset = set([])
# Traverse the first set and store its elements in hash
for i in range (n1):
myset.add(set1[i])
# Traverse the second set and check if any element of it is already in hash or not.
for i in range (n2):
if (set2[i] in myset):
return False
return True
if __name__ == "__main__":
set1 = [1, 2, 3, 4, 5]
set2 = [6, 7, 8, 3]
n1 = len(set1)
n2 = len(set2)
if (checkDisjoint(set1, set2, n1, n2)):
print ("Disjoint Set")
else:
print("Not a Disjoint Set")
Output:
Time Complexity
O(M+N): Where â€˜Mâ€™&â€™Nâ€™ stands for the length of the array as provided in the problem statement of the Check If Two Given Sets Are Disjoint.
Reason: As we are iterating through both input arrays once, assuming methods of HashSet are working in O(1) time.
Auxiliary Space Complexity
O(M+N): Where â€˜Mâ€™&â€™Nâ€™ stands for the length of the array as provided in the problem statement of the Check If Two Given Sets Are Disjoint.
Reason: The worstcase scenario is when every element is unique, thus assigning space for each element.
You can also read about the Longest Consecutive Sequence.
Frequently Asked Questions
What does a disjoint set mean?
The term "disjoint sets" refers to a pair of sets that do not share any elements.
What are the various names of Disjoint Set Data Structures?
The unionfind data structure and mergefind set are other names for the disjoint set data structure.
Are mutually exclusive and disjoint the same thing?
Events that never occur at the same moment are referred to as disjoint events. These are also referred to as occurrences that cannot coexist.
What does disjoint set rank mean?
Not the number of nodes in the tree, but its depth is represented by rank. The overall rank stays the same when two trees with different ranks are joined together.
What does a disjoint set in an algorithm mean?
A disjointset data structure is a type of data structure that organizes a set of components into various distinct (nonoverlapping) subsets.
Conclusion
This article has gone through problems related to Hashing, we have discussed the question: Check If Two Given Sets Are Disjoint in multiple languages. To master the topic, check out some of our resources about hashmap, HashMap Implementation, and Introduction to HashMap.
Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations. Check out our articles in Library. You may also check out our course on the array.
Do upvote our blog to help other ninjas grow.
Happy Learning!