CoreTechED

Loading

Tag distinct elements

Learn to compute the union of two arrays in C: naive O((n+m)²) and hash set O(n+m) approaches with complete code examples and edge cases.
C Programming

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

ApproachTimeSpace
Naive (linear search dedupe)O((n+m)²)O(n+m) for result
Hash setO(n+m) averageO(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

  1. Naive: Append elements from a then b, scanning the result for duplicates. Simple, quadratic.
  2. Hash set: Insert all elements into a set (which deduplicates automatically). Extract results.
  3. Verification: sameSet compares 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

  1. Use a hash set for O(n+m) average performance.
  2. Allocate n + m capacity for the result.
  3. Size hash tables ≥ 2× the expected input.
  4. Cast negative keys to unsigned int.
  5. Handle empty arrays without crashing.
  6. Do not rely on output order.
  7. Free all dynamically allocated memory.
  8. Use size_t for allocation math.
  9. Test edge cases: empty, single, all-common, no-common, negatives.
  10. 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.