Tag C subset check

Check if an Array is Subset of Another Array in C: A Comprehensive Tutorial

Determining whether one array is a subset of another is a classic problem that tests your understanding of searching, sorting, and hashing. Given two arrays a[] (size m) and b[] (size n), the goal is to check whether every element of b[] appears in a[]. This problem has applications in database queries, permission checks, and set operations.

This tutorial provides an in-depth exploration of checking subset relationships in C: naive nested loops, sort + two pointers, hash set approach, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is a Subset?

Array b[] is a subset of a[] if every element of b[] is also present in a[].

Examples:

text

Input: a = [11, 1, 13, 21, 3, 7], b = [11, 3, 7, 1] Output: true Input: a = [1, 2, 3, 4, 5, 6], b = [1, 2, 4] Output: true Input: a = [10, 5, 2, 23, 19], b = [19, 5, 3] Output: false

Why This Problem Matters

• Set operations: Foundation for union, intersection, difference.
• Database queries: IN, EXISTS, JOIN operations.
• Permission checks: Verify access rights.
• Algorithm design: Compare O(m×n), O(m log m + n log n), and O(m + n) approaches.
• Interview preparation: Common coding interview question.

Assumptions

• Arrays are not sorted.
• Elements are distinct (no duplicates).
• No assumptions about relative sizes.

Approaches Overview

Approach	Time Complexity	Space Complexity
Naive nested loops	O(m × n)	O(1)
Sort + two pointers	O(m log m + n log n)	O(1) or O(log m + log n)
Hash set	O(m + n) average	O(m)

---

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

For each element of b[], search a[] linearly.

c

#include <stdio.h> #include <stdbool.h> bool isSubsetNaive(const int a[], int m, const int b[], int n) { for (int i = 0; i < n; i++) { bool found = false; for (int j = 0; j < m; j++) { if (b[i] == a[j]) { found = true; break; } } if (!found) return false; } return true; } int main(void) { int a[] = {11, 1, 13, 21, 3, 7}; int b[] = {11, 3, 7, 1}; int m = sizeof(a) / sizeof(a[0]); int n = sizeof(b) / sizeof(b[0]); printf("%s\n", isSubsetNaive(a, m, b, n) ? "true" : "false"); return 0; }

Expected output:

text

true

Time: O(m × n), Space: O(1)

Approach 2: Sort + Two Pointers

Sort both arrays, then advance two pointers.

c

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> int compareInts(const void *x, const void *y) { int a = *(const int *)x; int b = *(const int *)y; return (a > b) - (a < b); } bool isSubsetSorted(int a[], int m, int b[], int n) { if (n > m) return false; qsort(a, m, sizeof(int), compareInts); qsort(b, n, sizeof(int), compareInts); int i = 0, j = 0; while (i < m && j < n) { if (a[i] < b[j]) i++; else if (a[i] == b[j]) { i++; j++; } else return false; /* b[j] not in a */ } return (j == n); } int main(void) { int a[] = {11, 1, 13, 21, 3, 7}; int b[] = {11, 3, 7, 1}; int m = sizeof(a) / sizeof(a[0]); int n = sizeof(b) / sizeof(b[0]); printf("%s\n", isSubsetSorted(a, m, b, n) ? "true" : "false"); return 0; }

Expected output:

text

true

Time: O(m log m + n log n), Space: O(1) with in-place sort

Trade-off: Modifies input arrays. If preservation is needed, copy first.

Approach 3: Hash Set (Optimal)

Insert all a[] elements into a hash set; check each element of b[].

c

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #define TABLE_SIZE 4096 typedef struct { int *keys; int *occupied; int capacity; } HashSet; static unsigned int hashFunc(int key, int capacity) { return ((unsigned int)key) % (unsigned int)capacity; } HashSet *createHashSet(int capacity) { HashSet *set = malloc(sizeof(HashSet)); if (set == NULL) return NULL; set->keys = malloc(capacity * sizeof(int)); set->occupied = calloc(capacity, sizeof(int)); if (set->keys == NULL || set->occupied == NULL) { free(set->keys); free(set->occupied); free(set); return NULL; } set->capacity = capacity; return set; } void freeHashSet(HashSet *set) { if (set != NULL) { free(set->keys); free(set->occupied); free(set); } } int setContains(HashSet *set, int key) { unsigned int idx = hashFunc(key, set->capacity); int start = (int)idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return 1; idx = (idx + 1) % (unsigned int)set->capacity; if ((int)idx == start) break; } return 0; } void setInsert(HashSet *set, int key) { unsigned int idx = hashFunc(key, set->capacity); int start = (int)idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return; idx = (idx + 1) % (unsigned int)set->capacity; if ((int)idx == start) return; } set->keys[idx] = key; set->occupied[idx] = 1; } bool isSubsetHash(const int a[], int m, const int b[], int n) { if (n > m) return false; HashSet *set = createHashSet(TABLE_SIZE); if (set == NULL) return false; for (int i = 0; i < m; i++) setInsert(set, a[i]); bool result = true; for (int i = 0; i < n; i++) { if (!setContains(set, b[i])) { result = false; break; } } freeHashSet(set); return result; } int main(void) { int a[] = {11, 1, 13, 21, 3, 7}; int b[] = {11, 3, 7, 1}; int m = sizeof(a) / sizeof(a[0]); int n = sizeof(b) / sizeof(b[0]); printf("%s\n", isSubsetHash(a, m, b, n) ? "true" : "false"); return 0; }

Expected output:

text

true

Time: O(m + n) average, Space: O(m)

---

Full Practical Code Example with Explanation

This program compares all three approaches with verification and edge cases.

c

/** * subset_check.c * Checks if array b[] is a subset of array a[]. * Compares naive, sort+two-pointer, and hash set approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 #define TABLE_SIZE 262144 /* 2^18 */ /* ---------- Approach 1: Naive ---------- */ bool isSubsetNaive(const int a[], int m, const int b[], int n) { if (n > m) return false; for (int i = 0; i < n; i++) { bool found = false; for (int j = 0; j < m; j++) { if (b[i] == a[j]) { found = true; break; } } if (!found) return false; } return true; } /* ---------- Approach 2: Sort + Two Pointers ---------- */ static int compareInts(const void *x, const void *y) { int a = *(const int *)x; int b = *(const int *)y; return (a > b) - (a < b); } bool isSubsetSorted(const int a_in[], int m, const int b_in[], int n) { if (n > m) return false; int *a = malloc(m * sizeof(int)); int *b = malloc(n * sizeof(int)); if (a == NULL || b == NULL) { free(a); free(b); return false; } memcpy(a, a_in, m * sizeof(int)); memcpy(b, b_in, n * sizeof(int)); qsort(a, m, sizeof(int), compareInts); qsort(b, n, sizeof(int), compareInts); int i = 0, j = 0; while (i < m && j < n) { if (a[i] < b[j]) i++; else if (a[i] == b[j]) { i++; j++; } else { free(a); free(b); return false; } } free(a); free(b); return (j == n); } /* ---------- Approach 3: Hash Set ---------- */ typedef struct { int *keys; int *occupied; int capacity; } HashSet; static unsigned int hashFunc(int key, int capacity) { return ((unsigned int)key) % (unsigned int)capacity; } HashSet *createHashSet(int capacity) { HashSet *set = malloc(sizeof(HashSet)); if (set == NULL) return NULL; set->keys = malloc(capacity * sizeof(int)); set->occupied = calloc(capacity, sizeof(int)); if (set->keys == NULL || set->occupied == NULL) { free(set->keys); free(set->occupied); free(set); return NULL; } set->capacity = capacity; return set; } void freeHashSet(HashSet *set) { if (set != NULL) { free(set->keys); free(set->occupied); free(set); } } int setContains(HashSet *set, int key) { unsigned int idx = hashFunc(key, set->capacity); int start = (int)idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return 1; idx = (idx + 1) % (unsigned int)set->capacity; if ((int)idx == start) break; } return 0; } void setInsert(HashSet *set, int key) { unsigned int idx = hashFunc(key, set->capacity); int start = (int)idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return; idx = (idx + 1) % (unsigned int)set->capacity; if ((int)idx == start) return; } set->keys[idx] = key; set->occupied[idx] = 1; } bool isSubsetHash(const int a[], int m, const int b[], int n) { if (n > m) return false; HashSet *set = createHashSet(TABLE_SIZE); if (set == NULL) return false; for (int i = 0; i < m; i++) setInsert(set, a[i]); bool result = true; for (int i = 0; i < n; i++) { if (!setContains(set, b[i])) { result = false; break; } } freeHashSet(set); return result; } /* ---------- Utility ---------- */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } static void demoBasic(void) { printf("\n=== Sample Arrays ===\n"); int a1[] = {11, 1, 13, 21, 3, 7}; int b1[] = {11, 3, 7, 1}; int a2[] = {1, 2, 3, 4, 5, 6}; int b2[] = {1, 2, 4}; int a3[] = {10, 5, 2, 23, 19}; int b3[] = {19, 5, 3}; struct { int *a, *b; int m, n; } tests[] = { {a1, b1, 6, 4}, {a2, b2, 6, 3}, {a3, b3, 5, 3} }; int numTests = 3; for (int i = 0; i < numTests; i++) { printf("\nTest %d:\n", i + 1); printf(" a = "); printArray(tests[i].a, tests[i].m); printf(" b = "); printArray(tests[i].b, tests[i].n); printf(" Naive: %s\n", isSubsetNaive(tests[i].a, tests[i].m, tests[i].b, tests[i].n) ? "true" : "false"); printf(" Sorted: %s\n", isSubsetSorted(tests[i].a, tests[i].m, tests[i].b, tests[i].n) ? "true" : "false"); printf(" Hash: %s\n", isSubsetHash(tests[i].a, tests[i].m, tests[i].b, tests[i].n) ? "true" : "false"); } } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Empty b */ int a1[] = {1, 2, 3}; printf("\nEmpty b[]: %s\n", isSubsetHash(a1, 3, NULL, 0) ? "true" : "false"); /* Empty a, non-empty b */ int b2[] = {1}; printf("Empty a[], b[]={1}: %s\n", isSubsetHash(NULL, 0, b2, 1) ? "true" : "false"); /* b larger than a */ int a3[] = {1, 2}; int b3[] = {1, 2, 3}; printf("b[] larger than a[]: %s\n", isSubsetHash(a3, 2, b3, 3) ? "true" : "false"); /* Single element */ int a4[] = {5}; int b4[] = {5}; printf("Single element equal: %s\n", isSubsetHash(a4, 1, b4, 1) ? "true" : "false"); /* Negative values */ int a5[] = {-1, -5, 3, -10}; int b5[] = {-5, -1}; printf("Negative values: %s\n", isSubsetHash(a5, 4, b5, 2) ? "true" : "false"); /* Same array */ int a6[] = {1, 2, 3, 4}; printf("Same array: %s\n", isSubsetHash(a6, 4, a6, 4) ? "true" : "false"); } static void performanceTest(void) { printf("\n=== Performance Comparison (m=2000, n=1000) ===\n"); int m = 2000, n = 1000; int *a = malloc(m * sizeof(int)); int *b = malloc(n * sizeof(int)); if (a == NULL || b == NULL) { free(a); free(b); return; } srand(42); for (int i = 0; i < m; i++) a[i] = i * 3; for (int i = 0; i < n; i++) b[i] = i * 3; /* b subset of a */ clock_t start, end; double t; start = clock(); bool r1 = isSubsetNaive(a, m, b, n); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive: result=%s, time=%.3f ms\n", r1 ? "true" : "false", t); start = clock(); bool r2 = isSubsetSorted(a, m, b, n); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sorted: result=%s, time=%.3f ms\n", r2 ? "true" : "false", t); start = clock(); bool r3 = isSubsetHash(a, m, b, n); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash: result=%s, time=%.3f ms\n", r3 ? "true" : "false", t); printf("Verification: %s\n", (r1 == r2 && r2 == r3) ? "PASS" : "FAIL"); free(a); free(b); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Array Subset Check Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Edge Cases\n"); printf("3. Performance Comparison\n"); printf("4. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demoBasic(); break; case 2: demoEdgeCases(); break; case 3: performanceTest(); break; case 4: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice.\n"); break; } } return EXIT_SUCCESS; }

Explanation of Approaches

1. Naive: For each element of b, linearly search a. O(m × n).
2. Sort + Two Pointers: Sort both, advance pointers. O(m log m + n log n).
3. Hash Set: Insert a into hash set; check each b in O(1) average. O(m + n).

Expected Output (sample run)

text

=== Sample Arrays === Test 1: a = [11, 1, 13, 21, 3, 7] b = [11, 3, 7, 1] Naive: true Sorted: true Hash: true Test 2: a = [1, 2, 3, 4, 5, 6] b = [1, 2, 4] Naive: true Sorted: true Hash: true Test 3: a = [10, 5, 2, 23, 19] b = [19, 5, 3] Naive: false Sorted: false Hash: false === Edge Cases === Empty b[]: true Empty a[], b[]={1}: false b[] larger than a[]: false Single element equal: true Negative values: true Same array: true === Performance Comparison (m=2000, n=1000) === Naive: result=true, time=12.345 ms Sorted: result=true, time=0.456 ms Hash: result=true, time=0.234 ms Verification: PASS

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Forgetting the Size Check

If n > m, b cannot be a subset — return false immediately.

c

if (n > m) return false;

2. Duplicate Elements

The problem assumes distinct elements. If duplicates exist, hash set approach may fail without multiset semantics.

Solution: Use a multiset (count occurrences) if duplicates allowed.

3. Mutating Input Arrays

Sort-based approach modifies inputs.

Solution: Copy before sorting if preservation is required.

4. Hash Set Collisions

Linear probing handles collisions; size table generously.

Solution: Use table size ≥ 2× expected m.

5. Empty Arrays

• Empty b is trivially a subset → true.
• Empty a with non-empty b → false.

c

if (n == 0) return true; if (m == 0) return false;

6. Negative Values

Hash function must handle negatives.

c

return ((unsigned int)key) % capacity;

7. Integer Overflow in Hash

Large keys can overflow multiplication.

Solution: Use unsigned int arithmetic.

8. Memory Leaks

Free hash set arrays after use.

c

freeHashSet(set);

9. Two-Pointer Bounds

Careful with while (i < m && j < n) — result is j == n.

10. Memory Considerations

• Naive: O(1) extra space.
• Sorted: O(m + n) if copying; O(1) in-place.
• Hash: O(m) extra space.
• Hash approach is preferred for large arrays.

---

Summary & Best Practices

Checking if one array is a subset of another is a classic problem with three progressive solutions. The hash set approach offers the best O(m + n) average time; sorting is best when extra memory is constrained.

Key Takeaways

• Subset check: every element of b must be in a.
• Naive: O(m × n) — simple but slow.
• Sort + two pointers: O(m log m + n log n) — in-place, no extra memory.
• Hash set: O(m + n) average — fastest for large inputs.
• Handle edge cases: empty arrays, n > m, negatives.

Best Practices

1. Check n > m first to short-circuit.
2. Use hash set for O(m + n) average.
3. Use sort + two pointers when memory is tight.
4. Copy inputs if preservation is required for sort.
5. Handle negatives via unsigned cast in hash.
6. Size hash table at least 2× m.
7. Free all allocated memory.
8. Document whether duplicates are supported.
9. Test with edge cases: empty, single-element, same array.
10. Profile for large inputs.

By mastering subset checking, you’ll gain a practical foundation in set operations, hashing, and algorithm trade-offs.