 Explore Edit Edit

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

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.

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

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

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

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

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)

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

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(n)

Recommended Programs  