# Find whether an array is subset of another array

Posted in

Vinay Khatri
Last updated on September 10, 2024

## 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:

1. Initialize two arrays, array1, and array2.

2. Outer loop picks an element from array2 and goes into array1.

1. if the value is found, then search for the next value.

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 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();
}
```

#### 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 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");
}
}
```

#### 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 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")
```

### 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

1. Initialize the values in array1 and array2.
2. Use the Quick sort technique to sort the array1.
3. Pick an element from array2 and search for it in sorted array1.
2. 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";
}
```

#### 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");
}
}
```

#### 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")
```

### 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

1. Initialize two arrays, array1, and array2.
2. Sort array1 in ascending order.
3. Sort array2 in ascending order.
4. Compare every element:
1. If values are not the same, then return 0.
2. 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");
}
```

#### 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")
```

### 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

1. Initialize two arrays, array1, and array2.
2. Create a hashtable and store all the elements of array1 into it.
3. For every element in array2, search in the hashtable.
2. 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";
}
```

#### 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]))
}

//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");
}
}
```

#### 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):

# 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")
```

### 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

1. Initialize two arrays, array1, and array2.
2. Copy all the elements of array1 to set.
3. Store the size of the set in a variable.
4. Copy all the elements of array2 to the same set.
5. 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";
}
}
```

#### 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++)
{
}
s = s1.size();
for ( i = 0; i < len2; 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" );
}
}
```

#### 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) :

size = len(s)
for i in range(len2) :

if (len(s) == size) :
print("Array2 is a subset of Array1")

else :
print("Array2 is not a subset of Array1")
```

### 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

1. Initialize two arrays, array1, and array2.
2. Increase the frequency of every array element in array1.
3. Traverse through array2 and decrease the frequency if the array element is found.
1. 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";
}
```

#### 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");
}
}
```

#### 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")
```

### 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.