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)
        /* 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.
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);
  }
  /* 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.
Time Complexity : O(n)
Posted by
Labels: ,