Check if the given arrays are disjoint in C, C++, Java and Python | faceprep

Check if the given arrays are disjoint in C, C++, Java and Python | faceprep

The program to check if the given arrays are disjoint is discussed here. Two arrays are said to be disjoint if they have no elements in common.


Check if the given arrays are disjoint in C, C++, Java and Python


For example :nnarr1 = {1,2,3,4,5}narr2 = {6,7,8,9}nnarr1 and arr2 elements are unique and hence they are said to be disjoint.nnarr3 = {1,2,3,4,5}narr4 = {4,5,6,7}nnarr3 and arr4 are not disjoint as they have elements 4 and 5 in common.n


This problem can be solved in four different ways.

Method 1: An easier approach is using two loops. Outer loop to traverse array 1 and an inner loop to check if any of the array 2 elements are found in array 1.

Method 2: This method uses sorting. The first array is sorted and the binary search is done for each element in array 2.

Method 3: The arrays are sorted and merge type of process is done to check if any of the array 2 elements are found in array 1.

Method 4: Firstly, the array 1 elements are inserted into a hash table. Secondly, the second array is traversed to check if any of the array 2 elements are found in array 1.


Algorithm to check if the given arrays are disjoint

  • Use two loops.
  • Traverse the array 1 using the outer loop.
  • Use the inner loop to check if the elements in array 2 are found in array 1.
  • If at least one element of array 2 is found in array 1, return false. Else return true.


check-if-the-given-arrays-are-disjoint-in-c-c-java-and-python-faceprep

Program to check if the given arrays are disjoint

@@coding::1@@


Time complexity: O(m * n)


Algorithm using sorting and binary search

  • Sort the array 1.
  • For every element in the array 2, perform binary search and find if the element is found in the sorted array.
  • If any one element of array 2 is found in the sorted array, return false.
  • Else return true.

C++ program to check if the given arrays are disjoint or not is discussed below.

@@coding::2@@


Time Complexity: O(mLogm + nLogm) if quicksort has the best time complexity of mLogm.


If sorting is done at worst-case, then the time complexity will be O(m^2 + nLogm).



Algorithm using sorting and merging

  • Sort both the arrays.
  • Use Merge type of process to see if any one element of sorted array 2 is found in sorted array 1.
  • If any one element of sorted array 2 is found in sorted array 1, return false. Else, return true.

C++ program to check if the given arrays are disjoint or not using sorting and merging is given below.


@@coding::3@@


Time complexity: O(mLogm + nLogn)



Check if the given arrays are disjoint in C, C++, Java and Python


Algorithm using hashing

  • Create a hash table.
  • Traverse the first array and store the array elements in the hash table.
  • Traverser the second array and check if any element is present in the hash table.
  • If all the elements of array 2 are not found in array 1, return true. Else, return false.


C++ program to check if two given arrays are disjoint or not using hashing is discussed below


@@coding::4@@


Time complexity: O(n)


Recommended Programs







Check if the given arrays are disjoint in C, C++, Java and Python