Check if an Array is a Subset of Another in C, C++, Java & Python | FACE Prep

Determining whether one array is a subset of another is a common programming challenge in coding interviews and competitive exams. A subset means that all elements of one array are present in another array. This guide covers different methods to check if an array is a subset efficiently, including their time complexities and optimized implementations.

What Is a Subset in Arrays?

An array arr2 is considered a subset of another array arr1 if all elements in arr2 exist in arr1.

Example:

Input 1:

arr1 = {1, 2, 3, 4, 5}
arr2 = {3, 4, 5}

Output:

Yes, arr2 is a subset of arr1.

Input 2:

arr1 = {1, 2, 3, 4, 5}
arr2 = {1, 2, 9}

Output:

No, arr2 is not a subset of arr1.

Methods to Check If an Array Is a Subset

1. Using Nested Loops (Brute Force Approach)

Algorithm:

• Traverse arr2 using an outer loop.
• For each element in arr2, check if it exists in arr1 using an inner loop.
• If all elements of arr2 are found in arr1, return true; otherwise, return false.

Code Implementation:

#include <iostream>
using namespace std;

bool isSubset(int arr1[], int arr2[], int m, int n) {
    for (int i = 0; i < n; i++) {
        bool found = false;
        for (int j = 0; j < m; j++) {
            if (arr2[i] == arr1[j]) {
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {3, 4, 5};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    
    cout << (isSubset(arr1, arr2, m, n) ? "arr2 is a subset of arr1" : "arr2 is NOT a subset of arr1");
    return 0;
}

Time Complexity:

O(m * n), as each element of arr2 is compared with every element of arr1.

2. Sorting and Binary Search

Algorithm:

• Sort arr1 (the larger array).
• Use binary search to check if each element in arr2 exists in the sorted arr1.

Code Implementation:

#include <iostream>
#include <algorithm>
using namespace std;

bool binarySearch(int arr[], int size, int key) {
    int low = 0, high = size - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) return true;
        if (arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

bool isSubset(int arr1[], int arr2[], int m, int n) {
    sort(arr1, arr1 + m);
    for (int i = 0; i < n; i++) {
        if (!binarySearch(arr1, m, arr2[i])) return false;
    }
    return true;
}

Time Complexity:

O(m log m + n log m), faster than the brute force approach.

3. Sorting and Merge Process

Algorithm:

• Sort both arrays.
• Use a merge-like process to compare elements of arr1 and arr2.
• If all elements of arr2 are found in arr1, return true.

Code Implementation:

#include <iostream>
#include <algorithm>
using namespace std;

bool isSubset(int arr1[], int arr2[], int m, int n) {
    sort(arr1, arr1 + m);
    sort(arr2, arr2 + n);
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j]) i++;
        else if (arr1[i] == arr2[j]) { i++; j++; }
        else return false;
    }
    return (j == n);
}

Time Complexity:

O(m log m + n log n), effective for larger arrays.

4. Using Hashing (Most Efficient Approach)

Algorithm:

• Insert all elements of arr1 into a hash set.
• Traverse arr2 and check if each element exists in the hash set.

Code Implementation:

#include <iostream>
#include <unordered_set>
using namespace std;

bool isSubset(int arr1[], int arr2[], int m, int n) {
    unordered_set<int> hashSet(arr1, arr1 + m);
    for (int i = 0; i < n; i++) {
        if (hashSet.find(arr2[i]) == hashSet.end()) return false;
    }
    return true;
}

Time Complexity:

O(m + n), making it the most efficient solution.

Conclusion

Each method offers a different level of efficiency based on the input size and constraints. The hashing approach is the most optimal in terms of time complexity, while sorting-based methods work well when memory constraints are present. Nested loops should be avoided for large inputs due to their inefficiency.

CLICK HERE TO KNOW MORE OUR PROGRAM!