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

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

When solving programming problems, determining if one array is a subset of another is a common challenge. A subset means that all elements of one array are present in another array. This guide explains the concept with examples and provides four efficient methods, complete with code and time complexities.

What Does Subset Mean in Arrays?

An array arr2 is considered a subset of another array arr1 if all elements in arr2 are also present in arr1.

Example:

  • Input: arr1 = {1, 2, 3, 4, 5} arr2 = {3, 4, 5} Output: Yes, arr2 is a subset of arr1.
  • Input: 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

We’ll discuss four methods to solve this problem efficiently:
  1. Using Nested Loops
  2. Using Sorting and Binary Search
  3. Using Sorting and Merge Process
  4. Using Hashing

Method 1: Using Nested Loops

Nested LoopsAlgorithm:
  1. Traverse arr2 using an outer loop.
  2. For each element in arr2, check if it exists in arr1 using an inner loop.
  3. If all elements of arr2 are found in arr1, return true. Otherwise, return false.

Code:

cpp
#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]);if (isSubset(arr1, arr2, m, n)) cout << “arr2 is a subset of arr1”; else cout << “arr2 is NOT a subset of arr1”;return 0; }

Time Complexity:

  • O(m * n): Outer loop runs for n, and inner loop for m.

Method 2: Sorting and Binary Search

Algorithm:

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

Code:

cpp
#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; }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]);if (isSubset(arr1, arr2, m, n)) cout << “arr2 is a subset of arr1”; else cout << “arr2 is NOT a subset of arr1”;return 0; }

Time Complexity:

  • O(m log m + n log m)

Method 3: Sorting and Merge Process

Algorithm:

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

Code:

cpp
#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); }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]);if (isSubset(arr1, arr2, m, n)) cout << “arr2 is a subset of arr1”; else cout << “arr2 is NOT a subset of arr1”;return 0; }

Time Complexity:

  • O(m log m + n log n)

Method 4: Using Hashing

Algorithm:

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

Code:

cpp
#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; }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]);if (isSubset(arr1, arr2, m, n)) cout << “arr2 is a subset of arr1”; else cout << “arr2 is NOT a subset of arr1”;return 0; }

Time Complexity:

  • O(m + n): Efficient for large arrays.

Conclusion

By using these methods, you can efficiently check if one array is a subset of another. Each method has its use case depending on the array sizes and constraints. For the fastest solution, hashing is often the best choice.CLICK HERE TO KNOW MORE OUR PROGRAM!Find if an array is a subset of another array 
c