Union of Two Arrays in C: Naive vs Hash Set
Union of Two Arrays in C: A Comprehensive Tutorial
The union of two arrays is the set of all distinct elements that appear in either array (or both). It is one of the fundamental set operations and appears frequently in database queries, permission systems, and data analysis. This tutorial explores two approaches in C: the naive O((n+m)²) version and the optimal O(n+m) hash-set version, each with a complete, portable implementation.
Conceptual Introduction & Fundamentals
What is the Union of Two Arrays?
The union of a[] and b[] is an array containing every distinct element that appears in a, in b, or in both. Duplicates are removed — each element appears exactly once.
Examples:
text
Input: a = [1, 2, 3, 2, 1], b = [3, 2, 2, 3, 3, 2] Output: [1, 2, 3] (order may vary) Input: a = [1, 2, 3], b = [4, 5, 6] Output: [1, 2, 3, 4, 5, 6]
Why This Problem Matters
- Set operations: Foundation for intersection, difference, symmetric difference.
- Database queries: SQL
UNION/UNION ALL. - Data analysis: Combined record sets across sources.
- Algorithm comparison: O((n+m)²) versus O(n+m).
- Interview preparation: Common coding interview question.
Approaches Overview
| Approach | Time | Space |
|---|---|---|
| Naive (linear search dedupe) | O((n+m)²) | O(n+m) for result |
| Hash set | O(n+m) average | O(n+m) |
Maximum Result Size
The union cannot exceed n + m elements, so allocate at least that much up front.
Syntax & Core Mechanics
Approach 1: Naive Linear Search
For each element of a and then b, scan the result array to see if it is already there.
c
#include <stdio.h> #include <stdlib.h> int *findUnionNaive(const int a[], int n, const int b[], int m, int *outSize) { if (n < 0 || m < 0 || outSize == NULL) return NULL; int *res = malloc((size_t)(n + m) * sizeof(int)); if (res == NULL) { *outSize = 0; return NULL; } int k = 0; /* Insert from a[] */ for (int i = 0; i < n; i++) { int found = 0; for (int j = 0; j < k; j++) { if (res[j] == a[i]) { found = 1; break; } } if (!found) res[k++] = a[i]; } /* Insert from b[] */ for (int i = 0; i < m; i++) { int found = 0; for (int j = 0; j < k; j++) { if (res[j] == b[i]) { found = 1; break; } } if (!found) res[k++] = b[i]; } *outSize = k; return res; } int main(void) { int a[] = {1, 2, 3, 2, 1}; int b[] = {3, 2, 2, 3, 3, 2}; int n = sizeof(a) / sizeof(a[0]); int m = sizeof(b) / sizeof(b[0]); int size = 0; int *result = findUnionNaive(a, n, b, m, &size); if (result != NULL) { for (int i = 0; i < size; i++) printf("%d ", result[i]); printf("\n"); free(result); } return 0; } Expected output:
text
1 2 3
Time: O((n+m)²), Space: O(n+m)
Approach 2: Hash Set (Optimal)
Insert both arrays into a hash set; extract the result.
c
#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 8192 typedef struct { int *keys; int *occupied; int capacity; int size; } HashSet; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } HashSet *createSet(int cap) { HashSet *s = malloc(sizeof(HashSet)); if (s == NULL) return NULL; s->keys = malloc((size_t)cap * sizeof(int)); s->occupied = calloc((size_t)cap, sizeof(int)); if (s->keys == NULL || s->occupied == NULL) { free(s->keys); free(s->occupied); free(s); return NULL; } s->capacity = cap; s->size = 0; return s; } void freeSet(HashSet *s) { if (s != NULL) { free(s->keys); free(s->occupied); free(s); } } int setInsert(HashSet *s, int key) { unsigned int idx = hashFunc(key, s->capacity); int start = (int)idx; while (s->occupied[idx]) { if (s->keys[idx] == key) return 0; /* Already present */ idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) return -1; /* Full */ } s->keys[idx] = key; s->occupied[idx] = 1; s->size++; return 1; } int *findUnionHash(const int a[], int n, const int b[], int m, int *outSize) { HashSet *set = createSet(TABLE_SIZE); if (set == NULL) { *outSize = 0; return NULL; } for (int i = 0; i < n; i++) setInsert(set, a[i]); for (int i = 0; i < m; i++) setInsert(set, b[i]); int *res = malloc((size_t)set->size * sizeof(int)); if (res == NULL) { *outSize = 0; freeSet(set); return NULL; } int k = 0; for (int i = 0; i < set->capacity; i++) { if (set->occupied[i]) res[k++] = set->keys[i]; } *outSize = k; freeSet(set); return res; } int main(void) { int a[] = {1, 2, 3, 2, 1}; int b[] = {3, 2, 2, 3, 3, 2}; int n = sizeof(a) / sizeof(a[0]); int m = sizeof(b) / sizeof(b[0]); int size = 0; int *result = findUnionHash(a, n, b, m, &size); if (result != NULL) { for (int i = 0; i < size; i++) printf("%d ", result[i]); printf("\n"); free(result); } return 0; } Expected output (order may vary):
text
1 2 3
Time: O(n+m) average, Space: O(n+m)
Why Hash Sets Work
The set guarantees uniqueness by returning 0 on duplicate insert. Once all elements are inserted, we walk the set (or its hash table) to build the result array.
Full Practical Code Example with Explanation
This program compares both approaches and verifies that the results match as sets.
c
/** * array_union.c * Computes the union of two arrays (distinct elements in either). * Compares naive and hash set approaches, verifies equality. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define TABLE_SIZE 262144 /* 2^18 */ /* ============================================================ * HashSet (linear probing) * ============================================================ */ typedef struct { int *keys; int *occupied; int capacity; int size; } HashSet; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } HashSet *createSet(int cap) { HashSet *s = malloc(sizeof(HashSet)); if (s == NULL) return NULL; s->keys = malloc((size_t)cap * sizeof(int)); s->occupied = calloc((size_t)cap, sizeof(int)); if (s->keys == NULL || s->occupied == NULL) { free(s->keys); free(s->occupied); free(s); return NULL; } s->capacity = cap; s->size = 0; return s; } void freeSet(HashSet *s) { if (s) { free(s->keys); free(s->occupied); free(s); } } int setContains(HashSet *s, int key) { unsigned int idx = hashFunc(key, s->capacity); int start = (int)idx; while (s->occupied[idx]) { if (s->keys[idx] == key) return 1; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) break; } return 0; } int setInsert(HashSet *s, int key) { unsigned int idx = hashFunc(key, s->capacity); int start = (int)idx; while (s->occupied[idx]) { if (s->keys[idx] == key) return 0; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) return -1; } s->keys[idx] = key; s->occupied[idx] = 1; s->size++; return 1; } /* ============================================================ * Approach 1: Naive linear search dedupe * ============================================================ */ int *findUnionNaive(const int a[], int n, const int b[], int m, int *outSize) { if (outSize == NULL) return NULL; *outSize = 0; int total = n + m; if (total <= 0) return NULL; int *res = malloc((size_t)total * sizeof(int)); if (res == NULL) return NULL; int k = 0; for (int i = 0; i < n; i++) { int found = 0; for (int j = 0; j < k; j++) { if (res[j] == a[i]) { found = 1; break; } } if (!found) res[k++] = a[i]; } for (int i = 0; i < m; i++) { int found = 0; for (int j = 0; j < k; j++) { if (res[j] == b[i]) { found = 1; break; } } if (!found) res[k++] = b[i]; } *outSize = k; return res; } /* ============================================================ * Approach 2: Hash set based union * ============================================================ */ int *findUnionHash(const int a[], int n, const int b[], int m, int *outSize) { if (outSize == NULL) return NULL; *outSize = 0; HashSet *set = createSet(TABLE_SIZE); if (set == NULL) return NULL; for (int i = 0; i < n; i++) setInsert(set, a[i]); for (int i = 0; i < m; i++) setInsert(set, b[i]); int *res = malloc((size_t)set->size * sizeof(int)); if (res == NULL) { freeSet(set); return NULL; } int k = 0; for (int i = 0; i < set->capacity; i++) { if (set->occupied[i]) res[k++] = set->keys[i]; } *outSize = k; freeSet(set); return res; } /* ============================================================ * Utility: compare two arrays as sets * ============================================================ */ int sameSet(const int x[], int nx, const int y[], int ny) { if (nx != ny) return 0; HashSet *s = createSet(TABLE_SIZE); if (s == NULL) return -1; for (int i = 0; i < nx; i++) setInsert(s, x[i]); if (s->size != ny) { freeSet(s); return 0; } for (int j = 0; j < ny; j++) { if (!setContains(s, y[j])) { freeSet(s); return 0; } } freeSet(s); return 1; } 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("]"); } /* ============================================================ * Demos * ============================================================ */ static void demoBasic(void) { printf("\n=== Sample Arrays ===\n"); int a1[] = {1, 2, 3, 2, 1}; int b1[] = {3, 2, 2, 3, 3, 2}; int a2[] = {1, 2, 3}; int b2[] = {4, 5, 6}; int a3[] = {1, 1, 1}; int b3[] = {2, 2, 2}; struct { int *a; int n; int *b; int m; const char *label; } tests[] = { {a1, 5, b1, 6, "a=[1,2,3,2,1], b=[3,2,2,3,3,2]"}, {a2, 3, b2, 3, "a=[1,2,3], b=[4,5,6]"}, {a3, 3, b3, 3, "a=[1,1,1], b=[2,2,2]"} }; int nt = sizeof(tests) / sizeof(tests[0]); for (int t = 0; t < nt; t++) { printf("\nTest %d: %s\n", t + 1, tests[t].label); printf(" a = "); printArray(tests[t].a, tests[t].n); printf("\n b = "); printArray(tests[t].b, tests[t].m); printf("\n"); int s1 = 0, s2 = 0; int *r1 = findUnionNaive(tests[t].a, tests[t].n, tests[t].b, tests[t].m, &s1); int *r2 = findUnionHash(tests[t].a, tests[t].n, tests[t].b, tests[t].m, &s2); printf(" Naive: "); if (r1) { printArray(r1, s1); free(r1); } printf("\n"); printf(" Hash: "); if (r2) { printArray(r2, s2); free(r2); } printf("\n"); int s1b = 0, s2b = 0; int *r1b = findUnionNaive(tests[t].a, tests[t].n, tests[t].b, tests[t].m, &s1b); int *r2b = findUnionHash(tests[t].a, tests[t].n, tests[t].b, tests[t].m, &s2b); printf(" Verify: %s\n", sameSet(r1b, s1b, r2b, s2b) ? "PASS" : "FAIL"); free(r1b); free(r2b); } printf("\n"); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); int size = 0; /* Empty a */ int b1[] = {1, 2, 3}; int *r = findUnionHash(NULL, 0, b1, 3, &size); printf("Empty a: size=%d, result=", size); if (r) { printArray(r, size); free(r); } printf("\n"); /* Empty b */ int a2[] = {4, 5}; r = findUnionHash(a2, 2, NULL, 0, &size); printf("Empty b: size=%d, result=", size); if (r) { printArray(r, size); free(r); } printf("\n"); /* Both empty */ r = findUnionHash(NULL, 0, NULL, 0, &size); printf("Both empty: size=%d\n", size); if (r) free(r); /* All common */ int a3[] = {1, 2, 3}; int b3[] = {3, 2, 1}; r = findUnionHash(a3, 3, b3, 3, &size); printf("All common: size=%d, result=", size); if (r) { printArray(r, size); free(r); } printf("\n"); /* No common */ int a4[] = {1, 2}; int b4[] = {3, 4}; r = findUnionHash(a4, 2, b4, 2, &size); printf("No common: size=%d, result=", size); if (r) { printArray(r, size); free(r); } printf("\n"); /* Negatives */ int a5[] = {-1, -5, 3}; int b5[] = {-10, -1, 7}; r = findUnionHash(a5, 3, b5, 3, &size); printf("Negatives: size=%d, result=", size); if (r) { printArray(r, size); free(r); } printf("\n"); /* Zeros */ int a6[] = {0, 1}; int b6[] = {0, 2}; r = findUnionHash(a6, 2, b6, 2, &size); printf("Zeros: size=%d, result=", size); if (r) { printArray(r, size); free(r); } printf("\n"); /* Single element each, common */ int a7[] = {42}; int b7[] = {42}; r = findUnionHash(a7, 1, b7, 1, &size); printf("Single common: size=%d, result=", size); if (r) { printArray(r, size); free(r); } printf("\n"); } static void performanceTest(void) { printf("\n=== Performance Comparison ===\n"); /* Small for naive */ int smallN = 2000; int *sa = malloc((size_t)smallN * sizeof(int)); int *sb = malloc((size_t)smallN * sizeof(int)); if (!sa || !sb) { free(sa); free(sb); return; } srand(42); for (int i = 0; i < smallN; i++) { sa[i] = rand() % 4000; sb[i] = rand() % 4000; } clock_t start, end; double t; int size = 0; start = clock(); int *r1 = findUnionNaive(sa, smallN, sb, smallN, &size); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (n=%d): size=%d, time=%.3f ms\n", smallN, size, t); free(r1); start = clock(); int *r2 = findUnionHash(sa, smallN, sb, smallN, &size); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=%d): size=%d, time=%.3f ms\n", smallN, size, t); free(r2); free(sa); free(sb); /* Large for hash */ int largeN = 1000000; int *la = malloc((size_t)largeN * sizeof(int)); int *lb = malloc((size_t)largeN * sizeof(int)); if (!la || !lb) { free(la); free(lb); return; } for (int i = 0; i < largeN; i++) { la[i] = rand() % 500000; lb[i] = rand() % 500000; } start = clock(); int *r3 = findUnionHash(la, largeN, lb, largeN, &size); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=1000000 each): size=%d, time=%.3f ms\n", size, t); free(r3); free(la); free(lb); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Union of Two Arrays Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate Both 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 the Approaches
- Naive: Append elements from
athenb, scanning the result for duplicates. Simple, quadratic. - Hash set: Insert all elements into a set (which deduplicates automatically). Extract results.
- Verification:
sameSetcompares two arrays as sets by inserting into a set and checking membership.
Expected Output (sample run)
text
=== Sample Arrays === Test 1: a=[1,2,3,2,1], b=[3,2,2,3,3,2] a = [1, 2, 3, 2, 1] b = [3, 2, 2, 3, 3, 2] Naive: [1, 2, 3] Hash: [1, 2, 3] Verify: PASS Test 2: a=[1,2,3], b=[4,5,6] a = [1, 2, 3] b = [4, 5, 6] Naive: [1, 2, 3, 4, 5, 6] Hash: [1, 2, 3, 4, 5, 6] Verify: PASS Test 3: a=[1,1,1], b=[2,2,2] a = [1, 1, 1] b = [2, 2, 2] Naive: [1, 2] Hash: [1, 2] Verify: PASS === Edge Cases === Empty a: size=3, result=[1, 2, 3] Empty b: size=2, result=[4, 5] Both empty: size=0 All common: size=3, result=[1, 2, 3] No common: size=4, result=[1, 2, 3, 4] Negatives: size=5, result=[-1, -5, 3, -10, 7] Zeros: size=3, result=[0, 1, 2] Single common: size=1, result=[42] === Performance Comparison === Naive (n=2000): size=2717, time=340.123 ms Hash (n=2000): size=2717, time=0.456 ms Hash (n=1000000 each): size=499851, time=298.765 ms
Common Pitfalls, Edge Cases & Memory Considerations
1. Forgetting to Deduplicate
Without the found check or a set, results contain duplicates.
2. Allocating Only max(n, m) Bytes
Union can be as large as n + m, so allocate accordingly.
c
int *res = malloc((size_t)(n + m) * sizeof(int)); /* Correct */
3. Hash Set Full
If the table is undersized, setInsert returns -1.
Solution: Size the table ≥ 2× (n + m).
4. Negative Keys
Cast to unsigned int before modulo.
5. Empty Arrays
Handle n == 0 or m == 0 gracefully.
6. Order of Output
The union’s order is unspecified; the problem allows any order.
7. Integer Overflow in Sizes
Use size_t when multiplying for allocation.
8. Memory Leaks
Free res and the set.
9. NULL Pointers
Guard against NULL inputs when n == 0 or m == 0.
10. Memory Considerations
- Naive: O(n + m) result array.
- Hash: O(n + m) for set plus result.
- Free all allocations on return.
Summary & Best Practices
The union of two arrays is a fundamental set operation. The hash set approach is optimal: deduplicate automatically, then emit results.
Key Takeaways
- Union contains all distinct elements from both arrays.
- Naive: O((n+m)²) — use for tiny inputs.
- Hash set: O(n+m) average — use by default.
- Result size ≤
n + m; allocate accordingly. - Order is unspecified; do not rely on it.
Best Practices
- Use a hash set for O(n+m) average performance.
- Allocate
n + mcapacity for the result. - Size hash tables ≥ 2× the expected input.
- Cast negative keys to
unsigned int. - Handle empty arrays without crashing.
- Do not rely on output order.
- Free all dynamically allocated memory.
- Use
size_tfor allocation math. - Test edge cases: empty, single, all-common, no-common, negatives.
- Profile for large inputs.
By mastering the union operation, you’ll be well prepared for intersection, difference, and other set-based problems in databases, data analysis, and system programming.
