Link copied to clipboard. Share away!

Dissmis

Published on 10 Mar 2020

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.

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

C

C++

Java

Python 3

Output

Input-
Enter the number of elements in array 1:5
Enter the elements of array 1: 1 2 3 4 5
Enter the number of elements in array 2:3
Enter the elements of array 2:3 4 5
Output-
Array 2 is a subset of Array 1

**Time Complexity: **O(m*n)

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

Output

Input-
Enter the number of elements in array 1:5
Enter the elements of array 1: 1 2 3 4 5
Enter the number of elements in array 2:3
Enter the elements of array 2:3 4 5
Output-
Array 2 is a subset of Array 1

**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).

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

C++

Output

Input-
Enter the number of elements in array 1:5
Enter the elements of array 1: 1 2 3 4 5
Enter the number of elements in array 2:3
Enter the elements of array 2:3 4 5
Output-
Array 2 is a subset of Array 1

**Time complexity:** O(mLogm + nLogn)

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

Output

**Time Complexity:** O(n)

*Recommended Programs*

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×