Find whether an array is subset of another array | Added Method 3 - GeeksforGeeks

Find whether an array is subset of another array | Added Method 3 - GeeksforGeeks
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.
Input: arr1[] = {11, 1, 13, 21, 3, 7}, arr2[] = {11, 3, 7, 1}
Output: arr2[] is a subset of arr1[]

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[].
Time Complexity: O(mLogm + nLogn) which is better than method 2

bool isSubset(int arr1[], int arr2[], int m, int n)

{

    int i = 0, j = 0;

     

    if(m < n)

       return 0;

 

    quickSort(arr1, 0, m-1);

    quickSort(arr2, 0, n-1);

    while( i < n && j < m )

    {

        if( arr1[j] <arr2[i] )

            j++;

        else if( arr1[j] == arr2[i] )

        {

            j++;

            i++;

        }

        else if( arr1[j] > arr2[i] )

            return 0;

    }

  

    if( i < n )

        return 0;

    else

        return 1;

}

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.

Note that method 1, method 2 and method 4 don’t handle the cases when we have duplicates in arr2[]. For example, {1, 4, 4, 2} is not a subset of {1, 4, 2}, but these methods will print it as a subset.

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.

Time Complexity: O(mLogm + nLogm).

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.

Time Complexity: O(m*n)

Read full article from Find whether an array is subset of another array | Added Method 3 - GeeksforGeeks