- Write a program to check whether one array is subset of another array or not.

Given two integer array Array1 and Array2 of size M and N(N <= M) respectively. We have to **check whether Array2 is subset of Aarray1 or not**.

An array A is subset of another array B, if each element of A is present in B.

For Example :Input Array1 : 3, 5, 7, 12, 1, 9, 10, 0, 2 Input Array2 : 1, 3, 5, 9 Array2 is subset of Array1 ----------------------------- Input Array1 : 3, 5, 7, 12, 1, 9, 10, 0, 2 Input Array2 : 6, 3, 8 Array2 is not a subset of Array1

Let Array1 and Array2 be two integer array of size M and N respectively and we want to check whether Array2 is subset of Array1 or not.

**Brute Force : O(M*N)**

- Search each element of Array2 in Array1 using linear search. If all elements of Array2 is present in Array1 then Array2 is subset of Array1 else not.

## C program to check whether one array is subset of another array

#include<stdio.h> /* Checks if array2 is subset of array1 */ int isSubsetArray(int *array1, int size1, int *array2, int size2) { int i, j; /* search every element of array2 in array1. If all elements of array 2 is found in array1 then array2 is subset of array1 otherwise not */ for (i = 0; i < size2; i++) { for (j = 0; j < size1; j++) { if(array2[i] == array1[j]) /* Element found */ break; } if(j == size1) /* array2[i] not found in array1 */ return 0; } /* All elements of array2 found in array1 */ return 1; } int main() { int array1[9] = {3, 5, 7, 12, 1, 9, 10, 0, 2}; int array2[4] = {1, 3, 5, 9}; if(isSubsetArray(array1, 9, array2, 4)) printf("array2 is subset of array1"); else printf("array2 is not a subset of array1"); return 0; }Output

array2 is subset of array1

**By Sorting Array1**

We can improve the time complexity of above algorithm by first sorting Array1. Now, we can search each element of Array2 in Array1 using binary search.

- Sort Array1. O(MLogM)
- Search each element of Array2 in sorted Array1 using binary search. NLogM
- If all elements of Array2 is present in Array1 then Array2 is subset of Array1 else not.

#include<stdio.h> /* Swap array element at index left and right */ void swap(int array[], int left, int right) { int temp; /* Swapping using a temp variable */ temp = array[left]; array[left]=array[right]; array[right]=temp; } void quickSort(int array[], int left, int right) { int pivot; if (right > left) { /* Partition the given array into two segment by calling partion function */ pivot = partition(array, left, right); /* Recursively sort left and right sub array*/ quickSort(array, left, pivot-1); quickSort(array, pivot+1, right); } } int partition(int array[], int left, int right) { int temp = left; int pivot = array[left]; while(left < right) { /* From left side, search for a number greater than pivot element */ while(array[left] <= pivot) left++; /* From right side, search for a number less than pivot element */ while(array[right] > pivot) right--; /*Swap array[left] and array[right] */ if(left < right) swap(array, left, right); } /* Put pivot element in it's currect position '*/ array[temp] = array[right]; array[right] = pivot; /* Return partition index. All elements left of right index is < pivot whereas elements right side of right index are > pivot element */ return right; } /* Standard implementation of binary search */ int bSearch(int *array, int left, int right, int K) { if(right >= left) { int mid = (left + right)/2; /* k is equal to array[mid] */ if(array[mid] == K) return mid; else if(K > array[mid]) /* Search of right sub tree */ return bSearch(array, (mid + 1), right, K); else /* search on left sub tree */ return bSearch(array, left, (mid -1), K); } /* K not foundin array */ return -1; } /* Checks if array2 is subset of array1 */ int isSubsetArray(int *array1, int size1, int *array2, int size2) { int i, j; /* Sort array1 */ quickSort(array1, 0, size1-1); /* search every element of array2 in array1. If all elements of array 2 is found in array1 then array2 is subset of array1 otherwise not */ for (i = 0; i < size2; i++) { if(bSearch(array1, 0, size1, array2[i]) == -1) return 0; } /* All elements of array2 found in array1 */ return 1; } int main() { int array1[9] = {3, 5, 7, 12, 1, 9, 10, 0, 2}; int array2[4] = {1, 3, 5, 9}; if(isSubsetArray(array1, 9, array2, 4)) printf("array2 is subset of array1"); else printf("array2 is not a subset of array1"); return 0; }Output

array2 is subset of array1

**By Using Hashing**

- Create a hash table and initialize it with zero.
- Add each element of Array1 in hashtable.
- Traverse Array2 and for each element Array2[i] check of it exists in hashtable or not.
- If all elements of Array2 is present in hashtable then Array2 is subset of Array1 else not.