Find if an array is a subset of another array in C, C++, Java and Python | faceprep

Program to find if an array is a subset of another array is discussed here. If all the elements of array 2 are found in array 1, then array 2 is said to be a subset of array 1.

For example,

arr1 = {1,2,3,4,5}
arr2 = {3,4,5}

arr2 is a subset of arr1.

arr3 = {1,2,3,4,5}
arr4 = {1,2,9}

arr4 is not a subset of arr3.

This problem can be solved in four different ways.

Method  1: An easier approach using two loops. Outer loop to traverse array 1 and an inner loop to check if all the array 2 elements are found in array1.

Method 2: This method uses sorting. The first array is sorted and the binary search is done for each element in array 2. 

Method 3: The arrays are sorted and merge type of process is done to check if the array 2 elements are found in array 1.

Method 4:  Firstly, the array elements are inserted into a hash table. Secondly, the second array is traversed to check the number of occurrence of each element of array 2 in array 1. 

Algorithm to check if an array is a subset of another array

  • Use two loops.
  • Traverse the array using the outer loop.
  • Using the inner loop, check if the elements in array 2 are present in array 1.
  • If all the elements of array 2 are found in array 1, return true.
  • Else, return false.

Program to check if an array is a subset of another array

// C program to check if an array is a subset of another array

#include<bits/stdc++.h>

bool isSubset(int arr1[], int arr2[],
int m, int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
if(arr2[i] == arr1[j])
break;
}

if (j == m)
return 0;
}

return 1;
}

int main()
{
int m,n;
printf(“\nEnter the size of array 1 : “);
scanf(“%d”, &m);
printf(“\nEnter the size of array 2 : “);
scanf(“%d”, &n);
int arr1[m],arr2[n];
int i;
printf(“\nEnter the array 1 elements : “);
for(i=0;i<m;i++)
{
scanf(“%d”,&arr1[i]);
}
printf(“\nEnter the array 2 elements : “);
for(i=0;i<n;i++)
{
scanf(“%d”,&arr2[i]);
}

if(isSubset(arr1, arr2, m, n))
printf(“\nArray2 is a subset of Array1\n “);
else
printf(“\nArray2 is not a subset of Array1\n”);

getchar();
return 0;
}

// C++ program to check if an array is a subset of another array

#include<bits/stdc++.h>
using namespace std;

bool isSubset(int arr1[], int arr2[],
int m, int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
if(arr2[i] == arr1[j])
break;
}

if (j == m)
return 0;
}

return 1;
}

int main()
{
int m,n;
cout << “\nEnter the size of array 1 : “;
cin >> m;
cout << “\nEnter the size of array 2 : “;
cin >> n;
int arr1[m],arr2[n];
int i;
cout << “\nEnter the array 1 elements : “;
for(i=0;i<m;i++)
{
cin >> arr1[i];
}
cout << “\nEnter the array 2 elements : “;
for(i=0;i<n;i++)
{
cin >> arr2[i];
}

if(isSubset(arr1, arr2, m, n))
cout << “\nArray2 is a subset of Array1\n “;
else
cout << “\nArray2 is not a subset of Array1\n”;

getchar();
return 0;
}

// Java program to check if an array is a subset of another array

import java.util.*;

class Main
{
static boolean subset_arrays(int arr1[], int arr2[],
int m, int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
if(arr2[i] == arr1[j])
break;
}

if (j == m)
return false;
}

return true;
}

public static void main (String[] args)
{
int m,n,i;
int arr1[] = new int[10];
int arr2[] = new int[10];
Scanner sc = new Scanner(System.in);
System.out.print(“Enter the size of array 1 : “);
m = sc.nextInt();
System.out.print(“Enter the size of array 2 : “);
n = sc.nextInt();
System.out.print(“Input the array 1 elements : “);
for(i=0;i<n;i++)
{
arr1[i] = sc.nextInt();
}
System.out.print(“Input the array 2 elements : “);
for(i=0;i<m;i++)
{
arr2[i] = sc.nextInt();
}

if(subset_arrays(arr1,arr2,n,m))
System.out.print(“\nArray 2 is a subset of array 1\n”);
else
System.out.print(“\nArray 2 is not a subset of array 1\n”);
}
}

# python program to check if an array is a subset of another

def disjoint_arrays(arr1,arr2):
for i in range(0,len(arr1)):
for j in range(0,len(arr2)):
if(arr1[i] == arr2[j]):
break
if(j == len(arr2)):
return 0
return 1;

arr1 = [1,2,3,4,5]
arr2 = [3,4,5]
res = disjoint_arrays(arr1,arr2)
if(res == 1):
print(“Array 2 is a subset of array 1”)
else:
print(“Array 2 is not a subset of array 1”)

 

Time Complexity: O(m*n)

Algorithm using sorting and binary search

 

  • Sort the array 1  elements.
  • For every element in the array, perform binary search and find if the element is found in the sorted array.
  • If all the elements of the array are found in the sorted array, return true.
  • Else return false.
C++ program to check if an array is a subset of another using sorting and binary search is given below

// C++ program to check if an array is a subset of another array

#include<bits/stdc++.h>
using namespace std;

void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}

int partition(int A[], int start, int end)
{
int x = A[end];
int i = (start – 1);
int j;
for (j = start; j <= end – 1; j++)
{
if(A[j] <= x)
{
i++;
swap(&A[i], &A[j]);
}
}
swap (&A[i + 1], &A[end]);
return (i + 1);
}

void quick_sort(int A[], int start, int end)
{
int pivot;
if(start < end)
{
pivot = partition(A, start, end);
quick_sort(A, start, pivot – 1);
quick_sort(A, pivot + 1, end);
}
}

int binary_search(int arr[], int low,
int high, int x)
{
if(high >= low)
{
int mid = (low + high)/2;
if(( mid == 0 || x > arr[mid-1]) && (arr[mid] == x))
return mid;
else if(x > arr[mid])
return binary_search(arr, (mid + 1), high, x);
else
return binary_search(arr, low, (mid -1), x);
}
return -1;
}

bool isSubset(int arr1[], int arr2[],
int m, int n)
{
int i = 0;

quick_sort(arr1, 0, m-1);
for (i=0; i<n; i++)
{
if (binary_search(arr1, 0, m – 1,arr2[i]) == -1)
return 0;
}

return 1;
}

int main()
{
int m,n;
cout << “\nEnter the size of array 1 : “;
cin >> m;
cout << “\nEnter the size of array 2 : “;
cin >> n;
int arr1[m],arr2[n];
int i;
cout << “\nEnter the array 1 elements : “;
for(i=0;i<m;i++)
{
cin >> arr1[i];
}
cout << “\nEnter the array 2 elements : “;
for(i=0;i<n;i++)
{
cin >> arr2[i];
}

if(isSubset(arr1, arr2, m, n))
cout << “\nArray2 is a subset of Array1\n “;
else
cout << “\nArray2 is not a subset of Array1\n”;

getchar();
return 0;
}

Time Complexity: O(mLogm + nLogm) if quicksort has the best time complexity of mLogm.

If sorting is done at worst-case, then the time complexity will be O(m^2 + nLogm).

Algorithm using sorting and merging

  • Sort both the arrays.
  • Use Merge type of process to see if all elements of the sorted array are found in sorted array 1.
  • If all the elements of array 2 are found in array 1, return true. Else, return false.
C++ program to check if an array is a subset of another array using sorting and merging is given below .

#include <bits/stdc++.h>
using namespace std;

int isSubset(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
if (m < n)
return 0;

sort(arr1, arr1 + m);
sort(arr2, arr2 + n);
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;
}

return (i < n)? 0 : 1;
}

int main()
{
int m,n;
cout << “\nEnter the size of array 1 : “;
cin >> m;
cout << “\nEnter the size of array 2 : “;
cin >> n;
int arr1[m],arr2[n];
int i;
cout << “\nEnter the array 1 elements : “;
for(i=0;i<m;i++)
{
cin >> arr1[i];
}
cout << “\nEnter the array 2 elements : “;
for(i=0;i<n;i++)
{
cin >> arr2[i];
}

if(isSubset(arr1, arr2, m, n))
cout << “\nArray2 is a subset of Array1\n “;
else
cout << “\nArray2 is not a subset of Array1\n”;

getchar();
return 0;
}

Time complexity: O(mLogm + nLogn)

Algorithm using hashing

 

  • Create two hash tables for array 2 and array 1 where the value of the arrays will be stored in column 1 and their the count of each value will be stored in column 2 in the table.
  • Traverse the second array and check the number of occurrence of each element of array 2 in array 1.
  • If the number of occurrences is same, then return true else return false.

C++ program to check if an array is a subset of another using hashing is discussed below

// C++ program to check if an array is a subset of another array using hashing

#include <stdio.h>
#include <unordered_map>
using namespace std;

unordered_map <int,int> map1;
unordered_map <int,int> map2;

int isSubset(int n2,int array2[])
{
for(int i=0;i<n2;i++)
{
if(!map1[array2[i]])
{
return 0;
}
}
return 1;
}

int main()
{
int arr1[10],arr2[10],n1,n2;

map1.reserve(10);
map2.reserve(10);

printf(“\nEnter the number of elements in array 1: “);
scanf(“%d”,&n1);

printf(“\nEnter the elements of array 1: \n”);
for(int i=0;i<n1;i++)
{
scanf(“%d”,&arr1[i]);
map1[arr1[i]]++;
}

printf(“\nEnter the number of elements in array 2: “);
scanf(“%d”,&n2);

printf(“\nEnter the elements of array 2:\n”);
for(int i=0;i<n2;i++)
{
scanf(“%d”,&arr2[i]);
map2[arr2[i]]++;
}

if(isSubset(n2,arr2))
{
printf(“\nArray 2 is a subset of Array 1\n”);
}
else
{
printf(“\nArray 2 is not a subset of Array 1\n”);
}
return 0;
}

Time Complexity: O(n)

Output:

check if given array is a subset of another array