Tag array intersection

Remove Minimum Elements so No Common Elements Exist in Two Arrays (C Tutorial)

Given two arrays, find the minimum number of elements that must be removed (across both arrays combined) so that the resulting arrays have no common elements. This problem is a subtle twist on intersection counting — and the solution is remarkably elegant.

This tutorial covers the insight, two C implementations (two maps vs. single map), edge cases, and best practices.

Conceptual Introduction & Fundamentals

What is the Problem?

Given two arrays arr1[] (size n) and arr2[] (size m), find the minimum number of elements to remove (from either array) so that no value appears in both arrays.

Examples:

text

Input: arr1 = [2, 3, 4, 5, 8], arr2 = [1, 2, 3, 4] Output: 3 (remove 2, 3, 4 from one array) Input: arr1 = [1, 2, 3, 4], arr2 = [5, 6, 7] Output: 0 (no common elements)

Why This Problem Matters

• Set operations: Deepens understanding of intersection.
• Multiset reasoning: Frequencies matter, not just presence.
• Two implementation strategies: Two maps vs. one map.
• Real-world use: Data deduplication, cache invalidation, conflict resolution.
• Interview preparation: Common coding interview question.

Key Insight

For each value v present in both arrays with frequencies f1(v) in arr1 and f2(v) in arr2, we must remove all copies from one side (or split removals) so no copy remains in both arrays. The cheapest approach is to remove min(f1(v), f2(v)) copies — remove all copies from the side with fewer.

Summing over all common values:

text

answer = Σ over common values v of min(f1(v), f2(v))

Approaches Overview

Syntax & Core Mechanics

Approach 1: Two Hash Maps

Count frequencies in both arrays; sum min(f1, f2) for common values.

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 4096 typedef struct { int *keys; int *counts; int *occupied; int capacity; } FreqMap; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } FreqMap *createMap(int cap) { FreqMap *m = malloc(sizeof(FreqMap)); if (m == NULL) return NULL; m->keys = malloc((size_t)cap * sizeof(int)); m->counts = calloc((size_t)cap, sizeof(int)); m->occupied = calloc((size_t)cap, sizeof(int)); if (m->keys == NULL || m->counts == NULL || m->occupied == NULL) { free(m->keys); free(m->counts); free(m->occupied); free(m); return NULL; } m->capacity = cap; return m; } void freeMap(FreqMap *m) { if (m) { free(m->keys); free(m->counts); free(m->occupied); free(m); } } void increment(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) { m->counts[idx]++; return; } idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) return; } m->keys[idx] = key; m->counts[idx] = 1; m->occupied[idx] = 1; } int getCount(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) return m->counts[idx]; idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) break; } return 0; } long long minRemoveTwoMaps(const int a[], int n, const int b[], int m) { FreqMap *ma = createMap(TABLE_SIZE); FreqMap *mb = createMap(TABLE_SIZE); if (ma == NULL || mb == NULL) { freeMap(ma); freeMap(mb); return -1; } for (int i = 0; i < n; i++) increment(ma, a[i]); for (int i = 0; i < m; i++) increment(mb, b[i]); long long res = 0; for (int i = 0; i < ma->capacity; i++) { if (!ma->occupied[i]) continue; int v = ma->keys[i]; int c2 = getCount(mb, v); if (c2 > 0) { int c1 = ma->counts[i]; res += (c1 < c2) ? c1 : c2; } } freeMap(ma); freeMap(mb); return res; } int main(void) { int arr1[] = {2, 3, 4, 5, 8}; int arr2[] = {1, 2, 3, 4}; printf("%lld\n", minRemoveTwoMaps(arr1, 5, arr2, 4)); return 0; }

Expected output:

text

3

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

Approach 2: Single Hash Map (Optimal)

Count arr1 frequencies in one map; iterate arr2; when a value with positive count is found, decrement and add 1.

c

long long minRemoveSingleMap(const int a[], int n, const int b[], int m) { FreqMap *count = createMap(TABLE_SIZE); if (count == NULL) return -1; for (int i = 0; i < n; i++) increment(count, a[i]); long long res = 0; for (int i = 0; i < m; i++) { int c = getCount(count, b[i]); if (c > 0) { /* Decrement manually */ unsigned int idx = hashFunc(b[i], count->capacity); int start = (int)idx; while (count->occupied[idx]) { if (count->keys[idx] == b[i]) { count->counts[idx]--; break; } idx = (idx + 1) % (unsigned int)count->capacity; if ((int)idx == start) break; } res++; } } freeMap(count); return res; }

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

Step-by-Step Trace for arr1 = [1,2,3,4], arr2 = [2,3,4,5,8]

text

Insert into count: {1:1, 2:1, 3:1, 4:1} Iterate arr2: 2 → count[2] = 1 > 0 → decrement to 0, res = 1 3 → count[3] = 1 > 0 → decrement to 0, res = 2 4 → count[4] = 1 > 0 → decrement to 0, res = 3 5 → count[5] = 0 → skip 8 → count[8] = 0 → skip Return 3 ✓

Full Practical Code Example with Explanation

This program implements both approaches, cross-verifies them, and exercises edge cases.

c

/** * min_remove_no_common.c * Minimum elements to remove so no common elements exist. * Compares two-map and single-map approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define TABLE_SIZE 262144 /* ============================================================ * FreqMap * ============================================================ */ typedef struct { int *keys; int *counts; int *occupied; int capacity; } FreqMap; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } FreqMap *createMap(int cap) { FreqMap *m = malloc(sizeof(FreqMap)); if (m == NULL) return NULL; m->keys = malloc((size_t)cap * sizeof(int)); m->counts = calloc((size_t)cap, sizeof(int)); m->occupied = calloc((size_t)cap, sizeof(int)); if (m->keys == NULL || m->counts == NULL || m->occupied == NULL) { free(m->keys); free(m->counts); free(m->occupied); free(m); return NULL; } m->capacity = cap; return m; } void freeMap(FreqMap *m) { if (m) { free(m->keys); free(m->counts); free(m->occupied); free(m); } } void increment(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) { m->counts[idx]++; return; } idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) return; } m->keys[idx] = key; m->counts[idx] = 1; m->occupied[idx] = 1; } int getCount(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) return m->counts[idx]; idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) break; } return 0; } void decrement(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) { m->counts[idx]--; return; } idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) return; } } /* ============================================================ * Approaches * ============================================================ */ long long minRemoveTwoMaps(const int a[], int n, const int b[], int m) { FreqMap *ma = createMap(TABLE_SIZE); FreqMap *mb = createMap(TABLE_SIZE); if (ma == NULL || mb == NULL) { freeMap(ma); freeMap(mb); return -1; } for (int i = 0; i < n; i++) increment(ma, a[i]); for (int i = 0; i < m; i++) increment(mb, b[i]); long long res = 0; for (int i = 0; i < ma->capacity; i++) { if (!ma->occupied[i]) continue; int v = ma->keys[i]; int c2 = getCount(mb, v); if (c2 > 0) { int c1 = ma->counts[i]; res += (c1 < c2) ? c1 : c2; } } freeMap(ma); freeMap(mb); return res; } long long minRemoveSingleMap(const int a[], int n, const int b[], int m) { FreqMap *count = createMap(TABLE_SIZE); if (count == NULL) return -1; for (int i = 0; i < n; i++) increment(count, a[i]); long long res = 0; for (int i = 0; i < m; i++) { if (getCount(count, b[i]) > 0) { decrement(count, b[i]); res++; } } freeMap(count); return res; } /* ============================================================ * 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("]"); } static void demoBasic(void) { printf("\n=== Sample Arrays ===\n"); int a1[] = {2, 3, 4, 5, 8}; int b1[] = {1, 2, 3, 4}; int a2[] = {1, 2, 3, 4}; int b2[] = {5, 6, 7}; int a3[] = {1, 2, 2, 3}; int b3[] = {2, 2, 2, 4}; struct { int *a; int n; int *b; int m; const char *label; } tests[] = { {a1, 5, b1, 4, "arr1=[2,3,4,5,8], arr2=[1,2,3,4]"}, {a2, 4, b2, 3, "arr1=[1,2,3,4], arr2=[5,6,7]"}, {a3, 4, b3, 4, "arr1=[1,2,2,3], arr2=[2,2,2,4]"} }; 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(" arr1: "); printArray(tests[t].a, tests[t].n); printf("\n"); printf(" arr2: "); printArray(tests[t].b, tests[t].m); printf("\n"); long long r1 = minRemoveTwoMaps(tests[t].a, tests[t].n, tests[t].b, tests[t].m); long long r2 = minRemoveSingleMap(tests[t].a, tests[t].n, tests[t].b, tests[t].m); printf(" Two-map: %lld\n Single-map: %lld\n", r1, r2); printf(" Verify: %s\n", (r1 == r2) ? "PASS" : "FAIL"); } printf("\n"); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Empty arrays */ printf("Both empty: %lld / %lld\n", minRemoveTwoMaps(NULL, 0, NULL, 0), minRemoveSingleMap(NULL, 0, NULL, 0)); /* One empty */ int a1[] = {1, 2, 3}; printf("arr2 empty: %lld / %lld\n", minRemoveTwoMaps(a1, 3, NULL, 0), minRemoveSingleMap(a1, 3, NULL, 0)); /* Disjoint */ int a2[] = {1, 2}; int b2[] = {3, 4}; printf("Disjoint: %lld / %lld (expect 0)\n", minRemoveTwoMaps(a2, 2, b2, 2), minRemoveSingleMap(a2, 2, b2, 2)); /* Identical */ int a3[] = {5, 5, 5}; int b3[] = {5, 5, 5}; printf("Identical [5,5,5]: %lld / %lld (expect 3)\n", minRemoveTwoMaps(a3, 3, b3, 3), minRemoveSingleMap(a3, 3, b3, 3)); /* Different frequencies */ int a4[] = {1, 1, 1, 2}; int b4[] = {1, 2, 2, 2}; printf("Different freqs: %lld / %lld (expect min(3,1)+min(1,3)=2)\n", minRemoveTwoMaps(a4, 4, b4, 4), minRemoveSingleMap(a4, 4, b4, 4)); /* Single common element */ int a5[] = {7, 8, 9}; int b5[] = {10, 7, 11}; printf("Single common: %lld / %lld (expect 1)\n", minRemoveTwoMaps(a5, 3, b5, 3), minRemoveSingleMap(a5, 3, b5, 3)); /* Negatives */ int a6[] = {-1, -2, -3}; int b6[] = {-2, -3, -4}; printf("Negatives: %lld / %lld (expect 2)\n", minRemoveTwoMaps(a6, 3, b6, 3), minRemoveSingleMap(a6, 3, b6, 3)); /* Zero */ int a7[] = {0, 0, 1}; int b7[] = {0, 2}; printf("Zero: %lld / %lld (expect min(2,1)=1)\n", minRemoveTwoMaps(a7, 3, b7, 2), minRemoveSingleMap(a7, 3, b7, 2)); } static void performanceTest(void) { printf("\n=== Performance Comparison ===\n"); int n = 5000000, m = 5000000; int *a = malloc((size_t)n * sizeof(int)); int *b = malloc((size_t)m * sizeof(int)); if (a == NULL || b == NULL) { free(a); free(b); return; } srand(42); for (int i = 0; i < n; i++) a[i] = rand() % 200000; for (int i = 0; i < m; i++) b[i] = rand() % 200000; clock_t start, end; double t; start = clock(); long long r1 = minRemoveTwoMaps(a, n, b, m); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Two-map (n=%d, m=%d): result=%lld, time=%.3f ms\n", n, m, r1, t); start = clock(); long long r2 = minRemoveSingleMap(a, n, b, m); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Single-map (n=%d, m=%d): result=%lld, time=%.3f ms\n", n, m, r2, t); printf("Verify: %s\n", (r1 == r2) ? "PASS" : "FAIL"); free(a); free(b); } static int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) return -1; errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) return -1; if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) return -1; *outValue = (int)val; return 0; } static void demoInteractive(void) { int n, m; if (readInteger("Enter arr1 size (0-10000): ", &n) != 0 || n < 0 || n > 10000) { printf("Invalid size.\n"); return; } int *a = NULL; if (n > 0) { a = malloc((size_t)n * sizeof(int)); if (a == NULL) return; for (int i = 0; i < n; i++) { char p[40]; snprintf(p, sizeof(p), " arr1[%d]: ", i); if (readInteger(p, &a[i]) != 0) { free(a); return; } } } if (readInteger("Enter arr2 size (0-10000): ", &m) != 0 || m < 0 || m > 10000) { printf("Invalid size.\n"); free(a); return; } int *b = NULL; if (m > 0) { b = malloc((size_t)m * sizeof(int)); if (b == NULL) { free(a); return; } for (int i = 0; i < m; i++) { char p[40]; snprintf(p, sizeof(p), " arr2[%d]: ", i); if (readInteger(p, &b[i]) != 0) { free(a); free(b); return; } } } printf("\nMinimum removals: %lld\n", minRemoveSingleMap(a, n, b, m)); free(a); free(b); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Minimum Removals so No Common Elements 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. Interactive\n"); printf("5. 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: demoInteractive(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice.\n"); break; } } return EXIT_SUCCESS; }

Explanation of the Approaches

1. Two maps: Count frequencies of both arrays; for each shared value, add min(f1, f2).
2. Single map: Count arr1; iterate arr2 and decrement each found value, adding 1 per match.

Both compute the same sum. The single map saves memory and cache pressure.

Expected Output (sample run)

text

=== Sample Arrays === Test 1: arr1=[2,3,4,5,8], arr2=[1,2,3,4] arr1: [2, 3, 4, 5, 8] arr2: [1, 2, 3, 4] Two-map: 3 Single-map: 3 Verify: PASS Test 2: arr1=[1,2,3,4], arr2=[5,6,7] arr1: [1, 2, 3, 4] arr2: [5, 6, 7] Two-map: 0 Single-map: 0 Verify: PASS Test 3: arr1=[1,2,2,3], arr2=[2,2,2,4] arr1: [1, 2, 2, 3] arr2: [2, 2, 2, 4] Two-map: 2 Single-map: 2 Verify: PASS === Edge Cases === Both empty: 0 / 0 arr2 empty: 0 / 0 Disjoint: 0 / 0 (expect 0) Identical [5,5,5]: 3 / 3 (expect 3) Different freqs: 2 / 2 (expect min(3,1)+min(1,3)=2) Single common: 1 / 1 (expect 1) Negatives: 2 / 2 (expect 2) Zero: 1 / 1 (expect min(2,1)=1)

Common Pitfalls, Edge Cases & Memory Considerations

1. Forgetting Frequencies

Two arrays with the same value but different counts need careful handling.

c

arr1 = [1, 1, 1] arr2 = [1] → remove 1 (min(3, 1) = 1)

2. Using Sets Instead of Maps

A set ignores frequencies and overcounts.

Solution: Use frequency maps.

3. Counting Per Value vs. Total

The answer sums min(f1, f2) across all shared values, not just one.

4. Integer Overflow in Sum

For large arrays with many duplicates, the sum can exceed int.

Solution: Use long long.

5. Empty Arrays

Any of n = 0 or m = 0 yields 0 (no removals needed).

6. Hash Table Sizing

Undersized tables cause probe failures.

Solution: Size ≥ 2× distinct values.

7. Negative Keys

Cast to unsigned int in the hash function.

8. Mutating Input

Both approaches leave inputs intact.

9. decrement Call on Missing Key

Guard with getCount() > 0 before decrementing.

10. Memory Considerations

• Two maps: O(n + m) space.
• Single map: O(n) space — preferred.
• Free allocated memory.
• Use long long for the total.

Summary & Best Practices

The minimum-removals problem reduces to summing min(f1(v), f2(v)) over all shared values. The single-map approach achieves O(n + m) time and O(n) space.

Key Takeaways

• Answer = Σ min(f1(v), f2(v)) for v common to both arrays.
• Two maps: O(n + m) time, O(n + m) space.
• Single map: O(n + m) time, O(n) space — preferred.
• Remove from the side with fewer copies per value.
• Use long long for the total.

Best Practices

1. Use the single-map approach for better memory usage.
2. Track frequencies, not just membership.
3. Sum min(f1, f2) per common value.
4. Use long long for the answer.
5. Guard decrements with a positive count check.
6. Size hash tables ≥ 2× distinct values.
7. Cast negative keys to unsigned int.
8. Free all allocated memory.
9. Test edge cases: empty, disjoint, identical, unequal frequencies.
10. Profile for large inputs.

By mastering this problem, you’ll deepen your intuition for multiset operations, frequency counting, and set-theoretic reductions.