# Program to Check One Array is Subset of Another Array

• 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.
Time Complexity : O(O(M*N))

## 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)
return 0;
}

/* All elements of array2 found in array1 */
return 1;
}

int main() {
int array1 = {3, 5, 7, 12, 1, 9, 10, 0, 2};
int array2 = {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.
Time Complexity : O(MLogM + NLogM)
```#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);
}
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 = {3, 5, 7, 12, 1, 9, 10, 0, 2};
int array2 = {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.
Time Complexity : O(n)