Find whether an array is subset of another array
Last Updated :
05 Jul, 2024
Given two arrays arr1[] and arr2[] of size m and n respectively, the task is to determine whether arr2[] is a subset of arr1[]. Both arrays are not sorted, and elements are distinct.
Examples:
Input: arr1[] = {11, 1, 13, 21, 3, 7}, arr2[] = {11, 3, 7, 1}
Output: Yes
Input: arr1[] = {1, 2, 3, 4, 5, 6}, arr2[] = {1, 2, 4}
Output: Yes
Input: arr1[] = {10, 5, 2, 23, 19}, arr2[] = {19, 5, 3}
Output: No
Approaches to find whether an array is subset of another array:
[Naive approach] Using Nested Loops – O(m*n) time and O(1) auxiliary space
The very basic approach is to use two nested loops: the outer loop picks each element from arr2[], and the inner loop searches for this element in arr1[]. If an element from arr2[] is not found in arr1[] then returns false. If all elements in arr2[] are found in arr1[], the function returns true.
Code Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
// Checks if an array is a subset of another array.
bool isSubset(vector<int> & arr1, vector<int> & arr2, int m, int n) {
// Iterate over each element in the second array
for (int i = 0; i < n; i++) {
bool found = false;
// Check if the element exists in the first array
for (int j = 0; j < m; j++) {
if (arr2[i] == arr1[j]) {
found = true;
break;
}
}
// If any element is not found, return false
if (!found) return false;
}
// If all elements are found, return true
return true;
}
int main() {
vector<int> arr1 = {11, 1, 13, 21, 3, 7};
vector<int> arr2 = {11, 3, 7, 1};
int m = arr1.size();
int n = arr2.size();
if (isSubset(arr1, arr2, m, n)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
public class SubsetChecker {
public static boolean isSubset(int[] arr1, int[] arr2, int m, int n) {
// Iterate over each element in the second array
for (int i = 0; i < n; i++) {
boolean found = false;
// Check if the element exists in the first array
for (int j = 0; j < m; j++) {
if (arr2[i] == arr1[j]) {
found = true;
break;
}
}
// If any element is not found, return false
if (!found) return false;
}
// If all elements are found, return true
return true;
}
public static void main(String[] args) {
int[] arr1 = {11, 1, 13, 21, 3, 7};
int[] arr2 = {11, 3, 7, 1};
int m = arr1.length;
int n = arr2.length;
if (isSubset(arr1, arr2, m, n)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
def is_subset(arr1, arr2, m, n):
# Iterate over each element in the second array
for i in range(n):
found = False
# Check if the element exists in the first array
for j in range(m):
if arr2[i] == arr1[j]:
found = True
break
# If any element is not found, return false
if not found:
return False
# If all elements are found, return true
return True
if __name__ == "__main__":
arr1 = [11, 1, 13, 21, 3, 7]
arr2 = [11, 3, 7, 1]
m = len(arr1)
n = len(arr2)
if is_subset(arr1, arr2, m, n):
print("Yes")
else:
print("No")
function isSubset(arr1, arr2, m, n) {
// Iterate over each element in the second array
for (let i = 0; i < n; i++) {
let found = false;
// Check if the element exists in the first array
for (let j = 0; j < m; j++) {
if (arr2[i] === arr1[j]) {
found = true;
break;
}
}
// If any element is not found, return false
if (!found) return false;
}
// If all elements are found, return true
return true;
}
const arr1 = [11, 1, 13, 21, 3, 7];
const arr2 = [11, 3, 7, 1];
const m = arr1.length;
const n = arr2.length;
if (isSubset(arr1, arr2, m, n)) {
console.log("Yes");
} else {
console.log("No");
}
Time Complexity: O(m*n)
Auxiliary Space: O(1)
[Optimized Approach] Using Sorting & Two Pointers – O(m log m + n log n) time and O(1) auxiliary Space
An efficient method involves sorting both arrays and using a two-pointer technique. By sorting both arrays, we can traverse them simultaneously with two pointers. One pointer starts at the beginning of arr1[] and the other at the beginning of arr2[]. If the current element in arr1[] matches the current element in arr2[], we move both pointers forward. If the current element in arr1[] is smaller, we move the pointer in arr1[] forward to find a potential match. If the current element in arr1[] is larger, it means the element in arr2[] is not in arr1[], and we return false. If we successfully traverse all elements in arr2[], we return true.
Code Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
bool isSubset(vector<int>& arr1, vector<int>& arr2)
{
// Sort both arrays
sort(arr1.begin(), arr1.end());
sort(arr2.begin(), arr2.end());
int i = 0, j = 0;
// Traverse both arrays using two pointers
while (i < arr1.size() && j < arr2.size()) {
if (arr1[i] < arr2[j]) {
i++;
}
else if (arr1[i] == arr2[j]) {
i++;
j++;
}
else {
// If element in arr2 is not found in arr1
return false;
}
}
// If we have traversed all elements in arr2, it is a
// subset
return (j == arr2.size());
}
int main()
{
vector<int> arr1 = { 11, 1, 13, 21, 3, 7 };
vector<int> arr2 = { 11, 3, 7, 1 };
if (isSubset(arr1, arr2)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}
def is_subset(arr1, arr2):
# Sort both arrays in ascending order
arr1.sort()
arr2.sort()
i = 0
j = 0
# Traverse both arrays using two pointers
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
# Element in arr1 is smaller, move to the next element in arr1
i += 1
elif arr1[i] == arr2[j]:
# Element found in both arrays, move to the next element in both arrays
i += 1
j += 1
else:
# Element in arr2 not found in arr1, not a subset
return False
# If we have traversed all elements in arr2, it is a subset
return j == len(arr2)
# Example usage
arr1 = [11, 1, 13, 21, 3, 7]
arr2 = [11, 3, 7, 1]
if is_subset(arr1, arr2):
print("Yes")
else:
print("No")
using System;
using System.Collections.Generic;
using System.Linq;
public class SubsetChecker {
public static bool IsSubset(List<int> arr1,
List<int> arr2)
{
// Sort both arrays in ascending order
arr1.Sort();
arr2.Sort();
int i = 0;
int j = 0;
// Traverse both arrays using two pointers
while (i < arr1.Count && j < arr2.Count) {
if (arr1[i] < arr2[j]) {
// Element in arr1 is smaller, move to the
// next element in arr1
i++;
}
else if (arr1[i] == arr2[j]) {
// Element found in both arrays, move to the
// next element in both arrays
i++;
j++;
}
else {
// Element in arr2 not found in arr1, not a
// subset
return false;
}
}
// If we have traversed all elements in arr2, it is
// a subset
return j == arr2.Count;
}
public static void Main(string[] args)
{
List<int> arr1
= new List<int>() { 11, 1, 13, 21, 3, 7 };
List<int> arr2 = new List<int>() { 11, 3, 7, 1 };
if (IsSubset(arr1, arr2)) {
Console.WriteLine("Yes");
}
else {
Console.WriteLine("No");
}
}
}
function isSubset(arr1, arr2) {
// Sort both arrays in ascending order
arr1.sort((a, b) => a - b);
arr2.sort((a, b) => a - b);
let i = 0;
let j = 0;
// Traverse both arrays using two pointers
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
// Element in arr1 is smaller, move to the next element in arr1
i++;
} else if (arr1[i] === arr2[j]) {
// Element found in both arrays, move to the next element in both arrays
i++;
j++;
} else {
// Element in arr2 not found in arr1, not a subset
return false;
}
}
// If we have traversed all elements in arr2, it is a subset
return j === arr2.length;
}
// Example usage
const arr1 = [11, 1, 13, 21, 3, 7];
const arr2 = [11, 3, 7, 1];
if (isSubset(arr1, arr2)) {
console.log("Yes");
} else {
console.log("No");
}
Time Complexity: O(m log m + n log n)
Auxiliary Space: O(1)
[Expected Approach] Using Hashing – O(m + n) time and O(m) auxiliary space
We can use a hash set to store elements of arr1[], this will help us in constant time complexity searching. We first insert all elements of arr1[] into a hash set. Then, for each element in arr2[], we check if it exists in the hash set. If any element in arr2[] is not found in the hash set, we return false. Otherwise, if all elements are found, we return true.
Code Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
bool isSubsetUsingHashing(const vector<int>& arr1, const vector<int>& arr2) {
// Create a hash set and insert all elements of arr1
unordered_set<int> hashSet(arr1.begin(), arr1.end());
// Check each element of arr2 in the hash set
for (int num : arr2) {
if (hashSet.find(num) == hashSet.end()) {
return false;
}
}
// If all elements of arr2 are found in the hash set
return true;
}
// Driver code
int main() {
vector<int> arr1 = {1, 2, 3, 4, 5, 6, 7, 8};
vector<int> arr2 = {1, 2, 3, 1};
if (isSubsetUsingHashing(arr1, arr2)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
import java.util.HashSet;
import java.util.Set;
public class SubsetChecker {
public static boolean isSubsetUsingHashing(int[] arr1,
int[] arr2)
{
// Create a hash set and insert all elements of arr1
Set<Integer> hashSet = new HashSet<>();
for (int num : arr1) {
hashSet.add(num);
}
// Check each element of arr2 in the hash set
for (int num : arr2) {
if (!hashSet.contains(num)) {
return false;
}
}
// If all elements of arr2 are found in the hash set
return true;
}
public static void main(String[] args)
{
int[] arr1 = { 11, 1, 13, 21, 3, 7 };
int[] arr2 = { 11, 3, 7, 1 };
if (isSubsetUsingHashing(arr1, arr2)) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
}
def is_subset_using_hashing(arr1, arr2):
# Create a hash set and insert all elements of arr1
hash_set = set(arr1)
# Check each element of arr2 in the hash set
for num in arr2:
if num not in hash_set:
return False
# If all elements of arr2 are found in the hash set
return True
# Driver code
arr1 = [11, 1, 13, 21, 3, 7]
arr2 = [11, 3, 7, 1]
if is_subset_using_hashing(arr1, arr2):
print("Yes")
else:
print("No")
using System;
using System.Collections.Generic;
public class SubsetChecker
{
public static bool IsSubsetUsingHashing(List<int> arr1, List<int> arr2)
{
// Create a hash set and insert all elements of arr1
HashSet<int> hashSet = new HashSet<int>(arr1);
// Check each element of arr2 in the hash set
foreach (int num in arr2)
{
if (!hashSet.Contains(num))
{
return false;
}
}
// If all elements of arr2 are found in the hash set
return true;
}
public static void Main(string[] args)
{
List<int> arr1 = new List<int>() { 11, 1, 13, 21, 3, 7 };
List<int> arr2 = new List<int>() { 11, 3, 7, 1 };
if (IsSubsetUsingHashing(arr1, arr2))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
function isSubsetUsingHashing(arr1, arr2) {
// Create a hash set and insert all elements of arr1
const hashSet = new Set(arr1);
// Check each element of arr2 in the hash set
for (const num of arr2) {
if (!hashSet.has(num)) {
return false;
}
}
// If all elements of arr2 are found in the hash set
return true;
}
// Driver code
const arr1 = [11, 1, 13, 21, 3, 7];
const arr2 = [11, 3, 7, 1];
if (isSubsetUsingHashing(arr1, arr2)) {
console.log("Yes");
} else {
console.log("No");
}
Time Complexity: O(m + n), where m and n are the size of arr1 and arr2 respectively.
Auxiliary Space: O(m)