Check if array is subset of another array.
Write a program to find whether an array is a subset of another array or not.
Given arr1[] and arr2[], we need to find whether arr1[] is a subset of arr2[]. An array is called a subset of another if all of its elements are present in the other array.
Note: Array elements are assumed to be unique.
Examples:
Example 1:
Input: arr1[]= [1,3,4,5,2]
arr2[]= [2,4,3,1,7,5,15]
Output: arr1[] is a subset of arr2[]
Example 2:
Input: arr1[]= [1,3,4,5,2]
arr2[]= [4,5,2]
Output: arr1[] is not a subset of arr2[]
Example 3:
Input: arr1[]= [1,3,4,5,2]
arr2[]= [11,12,13,15,16]
Output: arr1[] is not a subset of arr2[]
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Using two loops
We can use two nested loops. The outer loop iterates over the elements of arr1[] and the inner loop checks for that element in arr2[] by simple linear search.
Code:
C++ Code
#include <iostream>
using namespace std;
bool isSubset(int arr1[], int m, int arr2[], int n){
if(m>n) return false;
for(int i=0; i<m; i++){
bool present=false;
for(int j=0; j<n;j++){
if(arr2[j]==arr1[i]){
present = true;
break;
}
}
if(present==false) return false;
}
return true;
}
int main() {
// your code goes here
int arr1[]={1,3,4,5,2};
int arr2[]={2,4,3,1,7,5,15};
int m= sizeof(arr1)/sizeof(arr1[0]);
int n= sizeof(arr2)/sizeof(arr2[0]);
bool ans= isSubset(arr1,m,arr2,n);
if(ans==true)
cout<<"arr1[] is a subset of arr2[]";
else cout<<"arr1[] is not a subset of arr2[]";
return 0;
}
Output:
arr1[] is a subset of arr2[]
Time Complexity: O(M*N)
Reason: The outer loop runs for M times and for every iteration inner loop runs N times.
Space Complexity: O(1)
Java Code
import java.io.*;
import java.util.*;
class takeuforward {
static boolean isSubset(int arr1[], int m, int arr2[], int n) {
if (m > n) return false;
for (int i = 0; i < m; i++) {
boolean present = false;
for (int j = 0; j < n; j++) {
if (arr2[j] == arr1[i]) {
present = true;
break;
}
}
if (present == false) return false;
}
return true;
}
public static void main(String[] args) {
int arr1[]={1,3,4,5,2};
int arr2[]={2,4,3,1,7,5,15};
int m = arr1.length;
int n = arr2.length;
boolean ans = isSubset(arr1, m, arr2, n);
if (ans == true)
System.out.print("arr1[] is a subset of arr2[]");
else System.out.print("arr1[] is not a subset of arr2[]");
}
}
Output:
arr1[] is a subset of arr2[]
Time Complexity: O(M*N)
Reason: The outer loop runs for M times and for every iteration inner loop runs N times.
Space Complexity: O(1)
Solution 2: Using Sorting and Binary Search
We can improve the time complexity by using sorting and binary search. We first sort the arr2[] array and then we can use set a loop to traverse the elements of arr1[] and search for them in arr2[] using binary search( as arr2[] is sorted)
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
bool bSearch(int elem, int arr[], int n){
int start=0;
int end= n-1;
while(start<=end){
int mid= (start+end)/2;
if(arr[mid]==elem)
return true;
else if(arr[mid]<elem)
start = mid+1;
else end= mid-1;
}
return false;
}
bool isSubset(int arr1[], int m, int arr2[], int n){
sort(arr2,arr2+n); // library function to sort the array
if(m>n) return false;
for(int i=0; i<m; i++){
bool present= bSearch(arr1[i],arr2,n);
if(present==false) return false;
}
return true;
}
int main() {
// your code goes here
int arr1[]={1,3,4,5,2};
int arr2[]={2,4,3,1,7,5,15};
int m= sizeof(arr1)/sizeof(arr1[0]);
int n= sizeof(arr2)/sizeof(arr2[0]);
bool ans= isSubset(arr1,m,arr2,n);
if(ans==true)
cout<<"arr1[] is a subset of arr2[]";
else cout<<"arr1[] is not a subset of arr2[]";
return 0;
}
Output:
arr1[] is a subset of arr2[]
Time Complexity: O(NlogN+ MlogN)
Reason: Time required to sort Array of length N + Searching M elements using Binary Search
Space Complexity: O(1)
Reason: We are not using any extra space
Java Code
import java.io.*;
import java.util.*;
class takeuforward {
static boolean bSearch(int elem, int arr[], int n) {
int start = 0;
int end = n - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == elem)
return true;
else if (arr[mid] < elem)
start = mid + 1;
else end = mid - 1;
}
return false;
}
static boolean isSubset(int arr1[], int m, int arr2[], int n) {
if (m > n) return false;
Arrays.sort(arr2);
for (int i = 0; i < m; i++) {
boolean present = bSearch(arr1[i], arr2, n);
if (present == false) return false;
}
return true;
}
public static void main(String[] args) {
int arr1[]={1,3,4,5,2};
int arr2[]={2,4,3,1,7,5,15};
int m = arr1.length;
int n = arr2.length;
boolean ans = isSubset(arr1, m, arr2, n);
if (ans == true)
System.out.print("arr1[] is a subset of arr2[]");
else System.out.print("arr1[] is not a subset of arr2[]");
}
}
Output:
arr1[] is a subset of arr2[]
Time Complexity: O(NlogN+ MlogN)
Reason: Time required to sort Array of length N + Searching M elements using Binary Search
Space Complexity: O(1)
Reason: We are not using any extra space
Solution 3: Using Hashing
We can further improve the time complexity by using hashing. We first store the elements of arr2[] in a hashmap and then we can set a loop to traverse the elements of arr1[] and search for them in arr2[] in constant time( from hashmap).
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
bool isSubset(int arr1[], int m, int arr2[], int n){
if(m>n) return false;
unordered_map<int,bool> mp;
for(int i=0; i<n; i++){
mp[arr2[i]] = true;
}
for(int j=0;j<m;j++){
if(mp.count(arr1[j])==0){
return false;
}
}
return true;
}
int main() {
// your code goes here
int arr1[]={1,3,4,5,2};
int arr2[]={2,4,3,1,7,5,15};
int m= sizeof(arr1)/sizeof(arr1[0]);
int n= sizeof(arr2)/sizeof(arr2[0]);
bool ans= isSubset(arr1,m,arr2,n);
if(ans==true)
cout<<"arr1[] is a subset of arr2[]";
else cout<<"arr1[] is not a subset of arr2[]";
return 0;
}
Output: arr1[] is a subset of arr2[]
Java Code
import java.io.*;
import java.util.*;
class takeuforward {
static boolean isSubset(int arr1[], int m, int arr2[], int n){
if(m>n) return false;
HashMap<Integer, Boolean> mp = new HashMap<Integer, Boolean>();
for(int i=0; i<n; i++){
mp.put(arr2[i],true);
}
for(int j=0;j<m;j++){
if(mp.containsKey(arr1[j])==false){
return false;
}
}
return true;
}
public static void main(String[] args) {
int arr1[]={1,3,4,5,2};
int arr2[]={2,4,3,1,7,5,15};
int m= arr1.length;
int n= arr2.length;
boolean ans= isSubset(arr1,m,arr2,n);
if(ans==true)
System.out.print("arr1[] is a subset of arr2[]");
else System.out.print("arr1[] is not a subset of arr2[]");
}
}
Output: arr1[] is a subset of arr2[]
Special thanks to Anshuman Sharma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article