How to check if two given sets are disjoint? - GeeksforGeeks
Given two sets represented by two arrays, how to check if the given two sets are disjoint or not? It may be assumed that the given arrays have no duplicates.
Method 2 (Use Sorting and Merging)
1) Sort first and second sets.
2) Use merge like process to compare elements.
Given two sets represented by two arrays, how to check if the given two sets are disjoint or not? It may be assumed that the given arrays have no duplicates.
Method 2 (Use Sorting and Merging)
1) Sort first and second sets.
2) Use merge like process to compare elements.
Method 3 (Use Sorting and Binary Search)
This is similar to method 1. Instead of linear search, we use Binary Search.
1) Sort first set.
2) Iterate through every element of second set, and use binary search to search every element in first set. If element is found return it.
This is similar to method 1. Instead of linear search, we use Binary Search.
1) Sort first set.
2) Iterate through every element of second set, and use binary search to search every element in first set. If element is found return it.
Time complexity of this method is O(mLogm + nLogm)
Method 4 (Use Binary Search Tree)
1) Create a self balancing binary search tree (Red Black, AVL, Splay, etc) of all elements in first set.
2) Iterate through all elements of second set and search every element in the above constructed Binary Search Tree. If element is found, return false.
3) If all elements are absent, return true.
1) Create a self balancing binary search tree (Red Black, AVL, Splay, etc) of all elements in first set.
2) Iterate through all elements of second set and search every element in the above constructed Binary Search Tree. If element is found, return false.
3) If all elements are absent, return true.
Time complexity of this method is O(mLogm + nLogm).
Method 5 (Use Hashing)
1) Create an empty hash table.
2) Iterate through the first set and store every element in hash table.
3) Iterate through second set and check if any element is present in hash table. If present, then return false, else ignore the element.
4) If all elements of second set are not present in hash table, return true
Read full article from How to check if two given sets are disjoint? - GeeksforGeeks1) Create an empty hash table.
2) Iterate through the first set and store every element in hash table.
3) Iterate through second set and check if any element is present in hash table. If present, then return false, else ignore the element.
4) If all elements of second set are not present in hash table, return true
