C++ Programming – Find whether an array is subset of another array

Given two arrays: arr1[0..m-1] and arr2[0..n-1]. Find whether arr2[] is a subset of arr1[] or not. Both the arrays are not in sorted order. It may be assumed that elements in both array are distinct.

Examples:
Input: arr1[] = {11, 1, 13, 21, 3, 7}, arr2[] = {11, 3, 7, 1}
Output: arr2[] is a subset of arr1[]

Input: arr1[] = {1, 2, 3, 4, 5, 6}, arr2[] = {1, 2, 4}
Output: arr2[] is a subset of arr1[]

Input: arr1[] = {10, 5, 2, 23, 19}, arr2[] = {19, 5, 3}
Output: arr2[] is not a subset of arr1[] [ad type=”banner”]

Method 1 (Simple)
Use two loops: The outer loop picks all the elements of arr2[] one by one. The inner loop linearly searches for the element picked by outer loop. If all elements are found then return 1, else return 0.

[pastacode lang=”cpp” manual=”%23include%3Cstdio.h%3E%0A%20%0A%2F*%20Return%201%20if%20arr2%5B%5D%20is%20a%20subset%20of%20arr1%5B%5D%20*%2F%0Abool%20isSubset(int%20arr1%5B%5D%2C%20int%20arr2%5B%5D%2C%20int%20m%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20i%20%3D%200%3B%0A%20%20%20%20int%20j%20%3D%200%3B%0A%20%20%20%20for%20(i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(j%20%3D%200%3B%20j%3Cm%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20if(arr2%5Bi%5D%20%3D%3D%20arr1%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F*%20If%20the%20above%20inner%20loop%20was%20not%20broken%20at%20all%20then%0A%20%20%20%20%20%20%20%20%20%20%20arr2%5Bi%5D%20is%20not%20present%20in%20arr1%5B%5D%20*%2F%0A%20%20%20%20%20%20%20%20if%20(j%20%3D%3D%20m)%0A%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F*%20If%20we%20reach%20here%20then%20all%20elements%20of%20arr2%5B%5D%20%0A%20%20%20%20%20%20are%20present%20in%20arr1%5B%5D%20*%2F%0A%20%20%20%20return%201%3B%0A%7D%0A%20%20%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr1%5B%5D%20%3D%20%7B11%2C%201%2C%2013%2C%2021%2C%203%2C%207%7D%3B%0A%20%20%20%20int%20arr2%5B%5D%20%3D%20%7B11%2C%203%2C%207%2C%201%7D%3B%0A%20%20%20%0A%20%20%20%20int%20m%20%3D%20sizeof(arr1)%2Fsizeof(arr1%5B0%5D)%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr2)%2Fsizeof(arr2%5B0%5D)%3B%0A%20%0A%20%20%20%20if(isSubset(arr1%2C%20arr2%2C%20m%2C%20n))%0A%20%20%20%20%20%20printf(%22arr2%5B%5D%20is%20subset%20of%20arr1%5B%5D%20%22)%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20printf(%22arr2%5B%5D%20is%20not%20a%20subset%20of%20arr1%5B%5D%22)%3B%20%20%20%20%20%20%0A%20%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]

Output:

arr2[] is subset of arr1[] 

Time Complexity: O(m*n)

[ad type=”banner”]

Method 2 (Use Sorting and Binary Search)

1) Sort arr1[] O(mLogm)
2) For each element of arr2[], do binary search for it in sorted arr1[].
         a) If the element is not found then return 0.
3) If all elements are present then return 1.

[pastacode lang=”cpp” manual=”%23include%3Cstdio.h%3E%0A%20%0A%2F*%20Fucntion%20prototypes%20*%2F%0Avoid%20quickSort(int%20*arr%2C%20int%20si%2C%20int%20ei)%3B%0Aint%20binarySearch(int%20arr%5B%5D%2C%20int%20low%2C%20int%20high%2C%20int%20x)%3B%0A%20%0A%2F*%20Return%201%20if%20arr2%5B%5D%20is%20a%20subset%20of%20arr1%5B%5D%20*%2F%0Abool%20isSubset(int%20arr1%5B%5D%2C%20int%20arr2%5B%5D%2C%20int%20m%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20i%20%3D%200%3B%0A%20%20%20%0A%20%20%20%20quickSort(arr1%2C%200%2C%20m-1)%3B%0A%20%20%20%20for%20(i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(binarySearch(arr1%2C%200%2C%20m-1%2C%20arr2%5Bi%5D)%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F*%20If%20we%20reach%20here%20then%20all%20elements%20of%20arr2%5B%5D%20%0A%20%20%20%20%20%20are%20present%20in%20arr1%5B%5D%20*%2F%0A%20%20%20%20return%201%3B%0A%7D%0A%20%20%0A%2F*%20FOLLOWING%20FUNCTIONS%20ARE%20ONLY%20FOR%20SEARCHING%20AND%20SORTING%20PURPOSE%20*%2F%0A%2F*%20Standard%20Binary%20Search%20function*%2F%0Aint%20binarySearch(int%20arr%5B%5D%2C%20int%20low%2C%20int%20high%2C%20int%20x)%0A%7B%0A%20%20if(high%20%3E%3D%20low)%0A%20%20%7B%0A%20%20%20%20int%20mid%20%3D%20(low%20%2B%20high)%2F2%3B%20%20%2F*low%20%2B%20(high%20-%20low)%2F2%3B*%2F%0A%20%20%0A%20%20%20%20%2F*%20Check%20if%20arr%5Bmid%5D%20is%20the%20first%20occurrence%20of%20x.%0A%20%20%20%20%20%20%20%20arr%5Bmid%5D%20is%20first%20occurrence%20if%20x%20is%20one%20of%20the%20following%0A%20%20%20%20%20%20%20%20is%20true%3A%0A%20%20%20%20%20%20%20%20(i)%20%20mid%20%3D%3D%200%20and%20arr%5Bmid%5D%20%3D%3D%20x%0A%20%20%20%20%20%20%20%20(ii)%20arr%5Bmid-1%5D%20%3C%20x%20and%20arr%5Bmid%5D%20%3D%3D%20x%0A%20%20%20%20%20*%2F%0A%20%20%20%20if((%20mid%20%3D%3D%200%20%7C%7C%20x%20%3E%20arr%5Bmid-1%5D)%20%26%26%20(arr%5Bmid%5D%20%3D%3D%20x))%0A%20%20%20%20%20%20return%20mid%3B%0A%20%20%20%20else%20if(x%20%3E%20arr%5Bmid%5D)%0A%20%20%20%20%20%20return%20binarySearch(arr%2C%20(mid%20%2B%201)%2C%20high%2C%20x)%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20return%20binarySearch(arr%2C%20low%2C%20(mid%20-1)%2C%20x)%3B%0A%20%20%7D%0A%20return%20-1%3B%0A%7D%20%20%0A%20%0Avoid%20exchange(int%20*a%2C%20int%20*b)%0A%7B%0A%20%20%20%20int%20temp%3B%0A%20%20%20%20temp%20%3D%20*a%3B%0A%20%20%20%20*a%20%20%20%3D%20*b%3B%0A%20%20%20%20*b%20%20%20%3D%20temp%3B%0A%7D%0A%20%20%0Aint%20partition(int%20A%5B%5D%2C%20int%20si%2C%20int%20ei)%0A%7B%0A%20%20%20%20int%20x%20%3D%20A%5Bei%5D%3B%0A%20%20%20%20int%20i%20%3D%20(si%20-%201)%3B%0A%20%20%20%20int%20j%3B%0A%20%20%0A%20%20%20%20for%20(j%20%3D%20si%3B%20j%20%3C%3D%20ei%20-%201%3B%20j%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if(A%5Bj%5D%20%3C%3D%20x)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20i%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20exchange(%26A%5Bi%5D%2C%20%26A%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20exchange%20(%26A%5Bi%20%2B%201%5D%2C%20%26A%5Bei%5D)%3B%0A%20%20%20%20return%20(i%20%2B%201)%3B%0A%7D%0A%20%20%0A%2F*%20Implementation%20of%20Quick%20Sort%0AA%5B%5D%20–%3E%20Array%20to%20be%20sorted%0Asi%20%20–%3E%20Starting%20index%0Aei%20%20–%3E%20Ending%20index%0A*%2F%0Avoid%20quickSort(int%20A%5B%5D%2C%20int%20si%2C%20int%20ei)%0A%7B%0A%20%20%20%20int%20pi%3B%20%20%20%20%2F*%20Partitioning%20index%20*%2F%0A%20%20%20%20if(si%20%3C%20ei)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20pi%20%3D%20partition(A%2C%20si%2C%20ei)%3B%0A%20%20%20%20%20%20%20%20quickSort(A%2C%20si%2C%20pi%20-%201)%3B%0A%20%20%20%20%20%20%20%20quickSort(A%2C%20pi%20%2B%201%2C%20ei)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%20%0A%2F*Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr1%5B%5D%20%3D%20%7B11%2C%201%2C%2013%2C%2021%2C%203%2C%207%7D%3B%0A%20%20%20%20int%20arr2%5B%5D%20%3D%20%7B11%2C%203%2C%207%2C%201%7D%3B%0A%20%20%20%0A%20%20%20%20int%20m%20%3D%20sizeof(arr1)%2Fsizeof(arr1%5B0%5D)%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr2)%2Fsizeof(arr2%5B0%5D)%3B%0A%20%0A%20%20%20%20if(isSubset(arr1%2C%20arr2%2C%20m%2C%20n))%0A%20%20%20%20%20%20printf(%22arr2%5B%5D%20is%20subset%20of%20arr1%5B%5D%20%22)%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20printf(%22arr2%5B%5D%20is%20not%20a%20subset%20of%20arr1%5B%5D%20%22)%3B%20%20%20%20%20%20%0A%20%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]

Time Complexity: O(mLogm + nLogm). Please note that this will be the complexity if an mLogm algorithm is used for sorting which is not the case in above code. In above code Quick Sort is sued and worst case time complexity of Quick Sort is O(m^2)

[ad type=”banner”]

Method 3 (Use Sorting and Merging )
1) Sort both arrays: arr1[] and arr2[] O(mLogm + nLogn)
2) Use Merge type of process to see if all elements of sorted arr2[] are present in sorted arr1[].

[pastacode lang=”cpp” manual=”%2F*%20Return%201%20if%20arr2%5B%5D%20is%20a%20subset%20of%20arr1%5B%5D%20*%2F%0Abool%20isSubset(int%20arr1%5B%5D%2C%20int%20arr2%5B%5D%2C%20int%20m%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20i%20%3D%200%2C%20j%20%3D%200%3B%0A%20%20%20%20%20%0A%20%20%20%20if(m%20%3C%20n)%0A%20%20%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%20quickSort(arr1%2C%200%2C%20m-1)%3B%0A%20%20%20%20quickSort(arr2%2C%200%2C%20n-1)%3B%0A%20%20%20%20while(%20i%20%3C%20n%20%26%26%20j%20%3C%20m%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if(%20arr1%5Bj%5D%20%3Carr2%5Bi%5D%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20j%2B%2B%3B%0A%20%20%20%20%20%20%20%20else%20if(%20arr1%5Bj%5D%20%3D%3D%20arr2%5Bi%5D%20)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20j%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20i%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%20if(%20arr1%5Bj%5D%20%3E%20arr2%5Bi%5D%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%7D%0A%20%20%0A%20%20%20%20if(%20i%20%3C%20n%20)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20return%201%3B%0A%7D%20″ message=”C++ Program” highlight=”” provider=”manual”/]

Time Complexity: O(mLogm + nLogn) which is better than method 2. Please note that this will be the complexity if an nLogn algorithm is used for sorting both arrays which is not the case in above code. In above code Quick Sort is sued and worst case time complexity of Quick Sort is O(n^2)

Method 4 (Use Hashing)
1) Create a Hash Table for all the elements of arr1[].
2) Traverse arr2[] and search for each element of arr2[] in the Hash Table. If element is not found then return 0.
3) If all elements are found then return 1.

[ad type=”banner”]