Optimal Solution for Array Subset Problem: A Comprehensive Guide

Checking if a Smaller Array is Completely Contained in a Larger Array ( Efficient Approach )

In this blog, we’ll walk through how to solve the problem of checking whether a smaller array (subset) is completely contained within a larger array using C++ efficiently. We’ll provide a step-by-step breakdown with relatable explanations to make the concept easy to grasp.

The Task

You have two arrays:

1. mainArray (the larger array)

2. subsetArray (the smaller array)

The goal is to check if every element in subsetArray is present in mainArray. Additionally, if an element occurs multiple times in subsetArray, it must appear at least that many times in mainArray.

---

Step-by-Step Approach

Using a Hash Map

We’ll use a hash map (unordered_map in C++) to store the number of times each element appears in mainArray. Think of this like keeping a count of how many times each element shows up in a ledger.

Checking the Subset

For each element in subsetArray, we’ll check the hash map. If the element exists and appears enough times, we reduce its count. If the element is missing or doesn’t appear enough times, we return "No."

Efficient Solution

By using a hash map, the lookup for each element is O(1) on average. This makes the entire solution run in O(n + m), where n is the size of mainArray and m is the size of subsetArray. This is much faster than brute-force methods!

Here’s the C++ code:

#include<iostream>
#include<vector>
#include<unordered_map>
#include<string>

std::string isSubset(std::vector<int> mainArray, std::vector<int> subsetArray) {
    std::unordered_map<int, int> elementCount;

    // Step 1: Count occurrences of elements in 'mainArray'
    for (auto element : mainArray) {
        elementCount[element]++;
    }

    // Step 2: Check if all elements of 'subsetArray' are in 'mainArray'
    for (auto subsetElement : subsetArray) {
        if (elementCount[subsetElement] > 0) {
            elementCount[subsetElement]--;
        } else {
            return "No"; // Element missing or not enough occurrences
        }
    }

    return "Yes"; // All elements found
}

int main() {
    std::vector<int> mainArray = {11, 7, 1, 13, 21, 3, 7, 3};
    std::vector<int> subsetArray = {11, 3, 21, 13};

    std::cout << isSubset(mainArray, subsetArray); // Output: Yes
}

---

Special Explanation with a Real-World Scenario – Taking Attendance

To make this logic easier to grasp, let’s compare this problem to something familiar—taking attendance in class.

Imagine:

• mainArray is your class list (the students who showed up).

• subsetArray is the list of students you expect to be present.

Step 1: Taking Attendance (Building the Hash Map)

Just like taking attendance, we first go through the class list (mainArray) and count how many times each student (element) shows up. This count is stored in a record book (our hash map).

Example:

mainArray = {11, 7, 1, 13, 21, 3, 7, 3}

The record book would look like this:

11: 1
7: 2
1: 1
13: 1
21: 1
3: 2

Step 2: Verifying the Subset (Checking Attendance)

Now, we check if every student in the subsetArray list (expected attendance) is present in the class list (mainArray). For each student:

• If they’re in the record book, we mark them present (reduce the count by 1).

• If they’re missing or marked off too many times, we return "No".

Example:

subsetArray = {11, 3, 21, 13}

• Student 11? ✅ Present.

• Student 3? ✅ Present (count reduced by 1).

• Student 21? ✅ Present.

• Student 13? ✅ Present.

Since everyone on the subsetArray list is accounted for, the result is "Yes".

---

Edge Cases

Let’s discuss a few special cases:

1. Empty Subset:
   If subsetArray is empty, the function should return "Yes" because an empty set is always a subset.

2. More Occurrences in Subset:
   If an element appears more times in subsetArray than in mainArray, the function should return "No".

Example:

std::vector<int> mainArray = {1, 2, 3};
std::vector<int> subsetArray = {1, 1}; // No, because '1' appears only once in mainArray

3. Missing Elements:
   If subsetArray contains an element that isn’t in mainArray at all, the function should return "No".

Example:

std::vector<int> mainArray = {11, 7, 1, 13, 21, 3, 7, 3};
std::vector<int> subsetArray = {11, 3, 21, 99}; // No, '99' is missing

---

Conclusion

In summary, checking if a smaller array is a subset of a larger one can be done efficiently using a hash map. By tracking occurrences of elements, we ensure each element in the subset appears the necessary number of times in the main array. This solution runs in O(n + m) time, making it far more optimal than brute-force methods.

Next time you encounter a subset-checking problem, remember this method—it’s quick, efficient, and easy to understand! Try testing this approach with your own datasets to see its power in action.

💡 Enjoyed this blog? Follow me for more coding tutorials, tips, and guides! 🚀