Problem Statement
Consider two arrays, array1 and array2. These arrays can contain both positive and negative values, including zero. The array may be unsorted. We need to find whether array2 is the subset of array1 or not, i.e., we need to check if array1 contains all the elements which are available in array2. If array1 contains all the elements which are available in array2, then return 1 else, return 0.
Examples
Example 1:
Input: Consider two arrays. array1[] = [10,8,5,61,6,0] array2[] = [8,6,0,5] Output: True
Explanation : As array1 contains every element present in array2, which are 8,6,0,5. So, array1 is a subset of array2 .
Example 2:
Input: Consider two arrays. array1[] = [15,16,23,2,91,89] array2[] = [2,76,16] Output: False
Explanation: Here, array1 has 2,16, which are present in array1, but 76 is not present in array1, so array1 is not a subset of array2.
Approach 1: Naive Approach
Consider the given two arrays and initialize them with array elements. Now, make two loops such that the outer loop picks an element from array2 and goes to the inner loop for searching the value in array1. This process continues till the outer loop reaches the end of array2.
Algorithm:
- Initialize two arrays, array1, and array2.
2. Outer loop picks an element from array2 and goes into array1.
- if the value is found, then search for the next value.
- if the value is not found, then return false.
3. If all the values are found, then return 1.
C++ Code
#include <bits/stdc++.h>
bool subsetchecker(int array1[], int array2[],int len1, int len2)
{
int i,j;
i = 0;
j = 0;
for (i = 0; i < len2; i++)
{
for (j = 0; j < len1; j++)
{
if (array2[i] == array1[j])
break;
}
if (j == len1)
return 0; //if value is not found then return 0
}
return 1; // returns 1 if array1 is a subset of array2
}
// Driver code
int main()
{
int len1,len2;
int array1[] = { 10,8,5,61,6,0 };
int array2[] = { 8,6,0,5};
len1 = sizeof(array1) / sizeof(array1[0]);
len2 = sizeof(array2) / sizeof(array2[0]);
if (subsetchecker(array1, array2, len1, len2))
printf("Array2 is a subset of Array1");
else
printf("Array2 is not a subset of Array1");
getchar();
}
Output
Java Code
class Main{
static boolean subsetchecker(int array1[],int array2[],int len1, int len2)
{
int i,j;
i = 0;
j = 0;
for (i = 0; i < len2; i++)
{
for (j = 0; j < len1; j++)
{
if (array2[i] == array1[j])
break;
}
if (j == len1)
return false; //if value is not found then return 0
}
return true; // returns 1 if array1 is a subset of array2
}
// Driver code
public static void main(String args[])
{
int array1[] = { 10,8,5,61,6,0 };
int array2[] = { 8,6,0,5 };
int len1 = array1.length;
int len2 = array2.length;
if (subsetchecker(array1, array2, len1, len2))
System.out.print("Array2 is a subset of Array1");
else
System.out.print("Array2 is not a subset of Array1");
}
}
Output
Python Code
def subsetchecker(array1, array2, len1, len2):
i,j = 0,0
for i in range(len2):
for j in range(len1):
if(array2[i] == array1[j]):
break
if (j == len1):
return 0 #if value is not found then return 0
return 1 #returns 1 if array1 is a subset of array2
# Driver code
if __name__ == "__main__":
array1 = [10,8,5,61,6,0]
array2 = [8,6,0,5]
len1 = len(array1)
len2 = len(array2)
if(subsetchecker(array1, array2, len1, len2)):
print("Array2 is a subset of Array1 ")
else:
print("Array2 is not a subset of Array1")
Output
Complexity Analysis
- Time Complexity: It takes O(m*n) time complexity.
- Space Complexity: It takes only O(1) space complexity.
Approach 2: Using Sorting and Binary Search
In this approach, we initially sort the array1 using a sorting technique, and then we pick an element from array2 and then search for the element in the sorted array1. If the element is found in the sorted array1, then we return 1; if the element is not present in the sorted array, then we return 2.
Algorithm
- Initialize the values in array1 and array2.
- Use the Quick sort technique to sort the array1.
-
Pick an element from array2 and search for it in sorted array1.
- If an element is not found, then return 0.
- If all elements are present, then return 1.
C++ Code
#include <bits/stdc++.h>
using namespace std;
void quickSort(int* arr, int si, int ei);
int binarySearch(int arr[], int low,int high, int x);
bool subsetchecker(int array1[], int array2[],int len1, int n)
{
int i = 0;
quickSort(array1, 0, len1 - 1);
for (i = 0; i < n; i++)
{
if (binarySearch(array1, 0, len1 - 1,array2[i])== -1)
return 0;
}
return 1; //All elements are present
}
int binarySearch(int arr[], int l,int high, int x)
{
if (high >= l)
{
/*low + (high - low)/2;*/
int mid = (l + high) / 2;
if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x))
return mid;
else if (x > arr[mid])
return binarySearch(arr, (mid + 1), high, x);
else
return binarySearch(arr, l, (mid - 1), x);
}
return -1;
}
void swap(int* a, int* b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
int partition(int Array[], int si, int ei)
{
int x1 = Array[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++) {
if (Array[j] <= x1) {
i++;
swap(&Array[i], &Array[j]);
}
}
swap(&Array[i + 1], &Array[ei]);
return (i + 1);
}
void quickSort(int Array[], int si, int ei)
{
int pi;
if (si < ei) {
pi = partition(Array, si, ei);
quickSort(Array, si, pi - 1);
quickSort(Array, pi + 1, ei);
}
}
/*Driver code */
int main()
{
int len1,len2;
int array1[] = {10,8,5,61,6,0};
int array2[] = {8,6,0,5};
len1 = sizeof(array1) / sizeof(array1[0]);
len2 = sizeof(array2) / sizeof(array2[0]);
if (subsetchecker(array1, array2, len1, len2))
cout << "Array2 is a subset of Array1";
else
cout << "Array2 is not a subset of Array1";
}
Output
Java Code
class Main {
static boolean subsetchecker(int array1[],int array2[], int len1,int len2)
{
int i = 0;
sort(array1, 0, len1 - 1);
for (i = 0; i < len2; i++)
{
if (binarySearch(array1,0, len1 - 1,array2[i]) == -1)
return false;
}
return true; //returns 1 if all elements are true
}
//Binary Search function
static int binarySearch(int arr[], int l, int h, int x1)
{
if (h >= l)
{
int mid;
mid = (l + h)/ 2;
if ((mid == 0 || x1 > arr[mid - 1]) && (arr[mid] == x1))
return mid;
else if (x1 > arr[mid])
return binarySearch(arr,(mid + 1), h,x1);
else
return binarySearch(arr, l,(mid - 1), x1);
}
return -1;
}
static int partition(int arr[], int l, int h)
{
int pivot,i,j;
pivot = arr[h];
i = (l - 1);
for (j = l; j < h; j++)
{
if (arr[j] <= pivot) //if current value is smaller than pivot
{
i++;
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
int t;
t = arr[i + 1];
arr[i + 1] = arr[h];
arr[h] = t;
return i + 1;
}
static void sort(int arr[], int l, int h)
{
if (l < h)
{
int pi = partition(arr, l, h);
sort(arr, l, pi - 1);
sort(arr, pi + 1, h);
}
}
// Driver Code
public static void main(String args[])
{
int array1[] = { 10,8,5,61,6,0 };
int array2[] = { 8,6,0,5 };
int len1 = array1.length;
int len2 = array2.length;
if (subsetchecker(array1, array2, len1, len2))
System.out.print("Array2 is a subset of Array1");
else
System.out.print("Array2 is not a subset of Array1");
}
}
Output
Python Code
def subsetchecker(array1, array2, len1, len2):
i = 0
quickSort(array1, 0, len1-1)
for i in range(len2):
if (binarySearch(array1, 0, len1 - 1, array2[i]) == -1):
return 0
return 1 #all elements are present
def binarySearch(arr, l, h, x1):
if(h >= l):
mid = (l + h)//2
if((mid == 0 or x1 > arr[mid-1]) and (arr[mid] == x1)):
return mid
elif(x1 > arr[mid]):
return binarySearch(arr, (mid + 1), h, x1)
else:
return binarySearch(arr, l, (mid - 1), x1)
return -1
def partition(Array, si, ei):
x1 = Array[ei]
i = (si - 1)
for j in range(si, ei):
if(Array[j] <= x1):
i += 1
Array[i], Array[j] = Array[j], Array[i]
Array[i + 1], Array[ei] = Array[ei], Array[i + 1]
return (i + 1)
def quickSort(Array, si, ei):
# Partitioning index
if(si < ei):
pi = partition(Array, si, ei)
quickSort(Array, si, pi - 1)
quickSort(Array, pi + 1, ei)
# Driver code
array1 = [10,8,5,61,6,0]
array2 = [8,6,0,5]
len1 = len(array1)
len2 = len(array2)
if(subsetchecker(array1, array2, len1, len2)):
print("Array2 is a subset of Array1 ")
else:
print("Array2 is not a subset of Array1")
Output
Complexity Analysis
- Time Complexity: It takes O(m^2) time complexity.
- Space Complexity: It takes O(1) space complexity.
Approach 3: Using Sorting and Merging
In this approach, we sort both arrays in ascending order. Then we compare every array element if the value is not matched, then we return 0 else, we return 1.
Algorithm
- Initialize two arrays, array1, and array2.
- Sort array1 in ascending order.
- Sort array2 in ascending order.
-
Compare every element:
- If values are not the same, then return 0.
- If all values are matched, then return 1.
C++ Code
#include <bits/stdc++.h>
using namespace std;
bool subsetchecker(int array1[], int array2[],int len1, int len2)
{
int i = 0, j = 0;
if (len1 < len2)
return 0;
//Sorting the arrays
sort(array1, array1 + len1);
sort(array2, array2 + len2);
while (i < len2 && j < len1)
{
if (array1[j] < array2[i])
j++;
else if (array1[j] == array2[i])
{
j++;
i++;
}
else if (array1[j] > array2[i])
return 0;
}
return (i < len2) ? false : true;
}
// Driver Code
int main()
{
int len1,len2;
int array1[] = {10,8,5,61,6,07};
int array2[] = {8,6,0,5};
len1 = sizeof(array1) / sizeof(array1[0]);
len2 = sizeof(array2) / sizeof(array2[0]);
if (subsetchecker(array1, array2, len1, len2))
printf("Array2 is a subset of Array1 ");
else
printf("Array2 is not a subset of Array1");
}
Output
Java Code
import java.util.Arrays;
class Main
{
static boolean subsetchecker(int array1[],int array2[], int len1,int len2)
{
int i = 0, j = 0;
if (len1 < len2)
return false;
Arrays.sort(array1); // sorts arr1
Arrays.sort(array2); // sorts arr2
while (i < len2 && j < len1)
{
if (array1[j] < array2[i])
j++;
else if (array1[j] == array2[i])
{
j++;
i++;
}
else if (array1[j] > array2[i])
return false;
}
if (i < len2)
return false;
else
return true;
}
// Driver Code
public static void main(String[] args)
{
int len1,len2;
int array1[] = { 11, 1, 13, 21, 3, 7 };
int array2[] = { 11, 3, 7, 1 };
len1 = array1.length;
len2 = array2.length;
if (subsetchecker(array1, array2, len1, len2))
System.out.println("Array2 is a subset of Array1");
else
System.out.println("Array2 is not a subset of Array1");
}
}
Output
Python Code
def subsetchecker(array1, array2, len1, len2):
i = 0
j = 0
if len1 < len2:
return 0
array1.sort()
array2.sort()
while i < len2 and j < len1:
if array1[j] < array2[i]:
j =j+1
elif array1[j] == array2[i]:
j =j+1
i =i+ 1
elif array1[j] > array2[i]:
return 0
return False if i < len2 else True
# Driver code
array1 = [10,8,5,61,6,0]
array2 = [8,6,0,5]
len1 = len(array1)
len2 = len(array2)
if subsetchecker(array1, array2, len1, len2) == True:
print("Array2 is a subset of Array1")
else:
print("Array2 is not a subset of Array1")
Output
Complexity Analysis
- Time Complexity: It takes O(n^2) time complexity.
- Space Complexity: It takes only O(1) space complexity.
Approach 4: Use Hashing
In this approach, we create a hashtable and store array 1 into it. Now traverse through every element in the array2 and search for it the hashtable. If the element is not found, then return 0 else, return 1.
Algorithm
- Initialize two arrays, array1, and array2.
- Create a hashtable and store all the elements of array1 into it.
-
For every element in array2, search in the hashtable.
- If the value is not found, then return 0.
- If all values are found, then return 1.
C++ Code
#include <bits/stdc++.h>
using namespace std;
bool subsetchecker(int array1[], int len1,int array2[], int len2)
{
set <int> hashset;
//hset stores all values
for (int i = 0; i < len1; i++)
{
hashset.insert(array1[i]);
}
//checking for all values in arr2
for (int i = 0; i < len2; i++)
{
if (hashset.find(array2[i]) == hashset.end())
return false;
}
return true;
}
// Driver Code
int main()
{
int len1,len2;
int array1[] = { 11, 1, 13, 21, 3, 7 };
int array2[] = { 11, 3, 7, 1 };
len1 = sizeof(array1) / sizeof(array1[0]);
len2 = sizeof(array2) / sizeof(array2[0]);
if (subsetchecker(array1, len1, array2, len2))
cout << "Array2 is a subset of Array1"<< "\n";
else
cout << "Array2 is not a subset of Array1"<< "\n";
}
Output
Java Code
import java.util.HashSet;
class Main
{
static boolean subsetchecker(int array1[],int array2[], int len1,int len2)
{
HashSet <Integer> hs = new HashSet<>();
// to store all values
for (int i = 0; i < len1; i++) {
if (!hs.contains(array1[i]))
hs.add(array1[i]);
}
//checking if all values are present
for (int i = 0; i < len2; i++)
{
if (!hs.contains(array2[i]))
return false;
}
return true;
}
// Driver Code
public static void main(String[] args)
{
int len1,len2;
int array1[] = {10,8,5,61,6,0};
int array2[] = {8,6,0,5};
len1 = array1.length;
len2 = array2.length;
if (subsetchecker(array1, array2, len1, len2))
System.out.println("Array2 is a subset of Array1");
else
System.out.println("Array2 is not a subset of Array1");
}
}
Output
Python Code
def subsetchecker(array1, len1, array2, len2):
# STL set for hashing
hs = set()
# hset stores all the values of arr1
for i in range(0, len1):
hs.add(array1[i])
# to check if all values are present
for i in range(0, len2):
if array2[i] in hs:
continue
else:
return False
return True
# Driver Code
if __name__ == '__main__':
array1 = [ 10,8,5,61,6,0 ]
array2 = [ 8,6,0,5 ]
len1 = len(array1)
len2 = len(array2)
if (subsetchecker(array1, len1, array2, len2)):
print("Array2 is a subset of Array1")
else:
print("Array2 is not a subset of Array1")
Output
Complexity Analysis
- Time Complexity: It takes log2n time complexity.
- Space Complexity: It takes O(n) space complexity.
Approach 5: Using Set
In this approach, we use a set to find if array1 is a subset of array2 or not. First, add all the elements of array1 to the set and save the size of the set in a variable ‘s’, now, insert all the elements of array2 to the same set. If the size of the set is the same as the ‘s’, then return 1 else, return 0.
Algorithm
- Initialize two arrays, array1, and array2.
- Copy all the elements of array1 to set.
- Store the size of the set in a variable.
- Copy all the elements of array2 to the same set.
- If (size == set_size): return 1 else return 0
C++ Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int len1,len2,i;
int array1[] = { 10,8,5,61,6,0 };
int array2[] = {8,6,0,5 };
len1 = sizeof(array1) / sizeof(array1[0]);
len2 = sizeof(array2) / sizeof(array2[0]);
unordered_set <int> s1;
for (i = 0; i < len1; i++)
{
s1.insert(array1[i]);
}
int p = s1.size();
for (i = 0; i < len2; i++)
{
s1.insert(array2[i]);
}
if (s1.size() == p) {
cout << "Array2 is a subset of Array1"<< "\n";
}
else {
cout << "Array2 is not a subset of Array1 "<< "\n";
}
}
Output
Java Code
import java.io.*;
import java.util.*;
class Main
{
public static void main (String[] args)
{
int len1,len2,s,i;
int array1[] = {10,8,5,61,6,0};
int array2[] = {8,6,0,5};
len1=array1.length;
len2=array2.length;
Set <Integer> s1 = new HashSet();
for ( i = 0; i < len1; i++)
{
s1.add(array1[i]);
}
s = s1.size();
for ( i = 0; i < len2; i++)
{
s1.add(array2[i]);
}
if (s1.size() == s)
System.out.println("Array2 is a subset of Array1");
else
System.out.println("Array2 is not a subset of Array1" );
}
}
Output
Python Code
array1 = [ 11, 1, 13, 21, 3, 7 ]
array2 = [ 11, 3, 7, 1 ]
len1 = len(array1)
len2 = len(array2)
s = set()
for i in range(len1) :
s.add(array1[i])
size = len(s)
for i in range(len2) :
s.add(array2[i])
if (len(s) == size) :
print("Array2 is a subset of Array1")
else :
print("Array2 is not a subset of Array1")
Output
Complexity Analysis
- Time Complexity: It takes (m+n) time complexity.
- Space Complexity: It takes O(1) space complexity.
Approach 6: Using Frequency Table
In this approach, we create a frequency table for all the elements of array1, and we search for array2 elements' frequency in the frequency table. If the element frequency is not found, then we return 0.
Algorithm
- Initialize two arrays, array1, and array2.
- Increase the frequency of every array element in array1.
-
Traverse through array2 and decrease the frequency if the array element is found.
- If an element is not found, then return 0.
- If all the elements are found, then return 1.
C++ Code
#include <bits/stdc++.h>
using namespace std;
bool subsetchecker(int array1[], int len1,int array2[], int len2)
{
// frequency table using STL
map<int, int> freq;
for (int i = 0; i < len1; i++)
{
freq[array1[i]]++;
}
for (int i = 0; i < len2; i++)
{
if (freq[array2[i]] > 0)
freq[array2[i]]--;
else
{
return false;
}
}
return true;
}
// Driver Code
int main()
{
int array1[] = { 10,8,5,61,6,0};
int array2[] = { 8,6,0,5};
int len1 = sizeof(array1) / sizeof(array1[0]);
int len2 = sizeof(array2) / sizeof(array2[0]);
if (subsetchecker(array1, len1, array2, len2))
cout << "Array2 is a subset of Array1 "<< "\n";
else
cout << "Array2 is not a subset of Array1"<< "\n";
}
Output
Java Code
import java.io.*;
import java.util.*;
class Main{
static boolean subsetchecker(int[] array1, int len1,int[] array2, int len2)
{
int i;
//Frequency Table using STL
HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();
for(i = 0; i < len1; i++)
{
freq.put(array1[i],freq.getOrDefault(array1[i], 0) + 1);
}
for(i = 0; i < len2; i++)
{
if (freq.getOrDefault(array2[i], 0) > 0)freq.put(array2[i],freq.get(array1[i]) - 1);
else
{
return false;
}
}
return true;
}
// Driver Code
public static void main(String[] args)
{
int len1,len2;
int[] array1 = { 11, 1, 13, 21, 3, 7 };
int[] array2 = { 11, 3, 7, 1 };
len1 = array1.length;
len2 = array2.length;
if (subsetchecker(array1, len1, array2, len2))
System.out.println("Array2 is a subset of Array1 ");
else
System.out.println("Array2 is not a subset of Array1");
}
}
Output
Python Code
def subsetchecker(array1, len1, array2, len2):
freq= {} #creates a frequency table
for i in range(0, len1):
if array1[i] in freq:
freq[array1[i]] = freq[array1[i]] + 1
else:
freq[array1[i]] = 1
for i in range(0, len2):
if (freq[array2[i]] > 0):
freq[array2[i]] -= 1
else:
return False
return True
# Driver Code
if __name__ == '__main__':
array1 = [10,8,5,61,6,0]
array2 = [8,6,0,5]
len1 = len(array1)
len2 = len(array2)
if (subsetchecker(array1, len1, array2, len2)):
print("Array2 is a subset of Array1")
else:
print("Array2 is not a subset of Array1")
Output
Complexity Analysis
- Time Complexity: It takes O(m*n) time complexity.
- Space Complexity: It takes only O(1) space complexity.
Conclusion
In this article, we discussed how to check if an array is a subset of another array by using the Naive approach, hashtable, set, arrays, and a few other data structures. We have also discussed the algorithm and code in C++, Java, and Python for the approaches. We hope this article helps you to solve the problem and its variants in a better and more efficient way.
Happy Coding!
People are also reading:
- Longest Palindromic Subsequence using Dynamic Programming
- Move all zeros present in an array to the end
- Rearrange an array such that arr[i] = i
- Sort an array in one swap whose two elements are swapped
- Program to Find LCM and HCF of two numbers
- Majority Element
- Write a Program to convert given inches into equivalent yard, and feet
- WAP to Print Square Using * Character
- Find ancestors of a given node in a Binary Tree
- Maximum size square sub-matrices with all 1’s
Leave a Comment on this Post