Check if Two Arrays Are Equal in C: Complete Guide

Check if Two Arrays Are Equal in C: A Comprehensive Tutorial

Determining whether two arrays are equal—regardless of order but with identical element counts—is a fundamental problem that appears in set comparison, data validation, and caching systems. This tutorial explores two primary approaches: sorting-based comparison (O(n log n)) and hash-based counting (O(n) average).

---

Conceptual Introduction & Fundamentals

What Does “Arrays Are Equal” Mean?

Two arrays are equal if:

• Both have the same length.
• Both contain the same multiset of elements (same elements with same counts).
• Order does not matter.

Examples:

text

Input: a = [1, 2, 5, 4, 0], b = [2, 4, 5, 0, 1] Output: true Input: a = [1, 2, 5, 4, 0, 2, 1], b = [2, 4, 5, 0, 1, 1, 2] Output: true Input: a = [1, 7, 1], b = [7, 7, 1] Output: false (a has two 1s, b has two 7s)

Why This Problem Matters

• Multiset comparison: Foundation for set operations with duplicates.
• Data validation: Verify input arrays match expected.
• Caching: Check cache-key equivalence.
• Testing: Assert expected outputs match actual.
• Interview preparation: Common coding interview question.

Approaches Overview

Approach	Time Complexity	Space Complexity
Sorting	O(n log n)	O(1) or O(n)
Hashing (frequency)	O(n) average	O(n)

Note: Simple linear comparison only works if arrays are already sorted or order must match.

---

Syntax & Core Mechanics

Approach 1: Sorting

Sort both arrays and compare element by element.

c

#include <stdio.h> #include <stdlib.h> #include <string.h> int compareInts(const void *x, const void *y) { int a = *(const int *)x; int b = *(const int *)y; return (a > b) - (a < b); } int arraysEqualSorted(const int a_in[], int n, const int b_in[], int m) { if (n != m) return 0; int *a = malloc(n * sizeof(int)); int *b = malloc(m * sizeof(int)); if (a == NULL || b == NULL) { free(a); free(b); return 0; } memcpy(a, a_in, n * sizeof(int)); memcpy(b, b_in, m * sizeof(int)); qsort(a, n, sizeof(int), compareInts); qsort(b, m, sizeof(int), compareInts); int result = 1; for (int i = 0; i < n; i++) { if (a[i] != b[i]) { result = 0; break; } } free(a); free(b); return result; } int main(void) { int a[] = {3, 5, 2, 5, 2}; int b[] = {2, 3, 5, 5, 2}; int n = sizeof(a) / sizeof(a[0]); int m = sizeof(b) / sizeof(b[0]); printf("%s\n", arraysEqualSorted(a, n, b, m) ? "true" : "false"); return 0; }

Expected output:

text

true

Time: O(n log n), Space: O(n) with copy, O(1) in-place

Approach 2: Hash Map (Frequency Counting)

Count occurrences in a; decrement counts using b.

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 8192 typedef struct { int *keys; int *counts; int *occupied; int capacity; } HashMap; static unsigned int hashFunc(int key, int capacity) { return ((unsigned int)key) % (unsigned int)capacity; } HashMap *createHashMap(int capacity) { HashMap *map = malloc(sizeof(HashMap)); if (map == NULL) return NULL; map->keys = malloc(capacity * sizeof(int)); map->counts = calloc(capacity, sizeof(int)); map->occupied = calloc(capacity, sizeof(int)); if (map->keys == NULL || map->counts == NULL || map->occupied == NULL) { free(map->keys); free(map->counts); free(map->occupied); free(map); return NULL; } map->capacity = capacity; return map; } void freeHashMap(HashMap *map) { if (map) { free(map->keys); free(map->counts); free(map->occupied); free(map); } } void increment(HashMap *map, int key) { unsigned int idx = hashFunc(key, map->capacity); int start = (int)idx; while (map->occupied[idx]) { if (map->keys[idx] == key) { map->counts[idx]++; return; } idx = (idx + 1) % (unsigned int)map->capacity; if ((int)idx == start) return; } map->keys[idx] = key; map->counts[idx] = 1; map->occupied[idx] = 1; } int getCount(HashMap *map, int key) { unsigned int idx = hashFunc(key, map->capacity); int start = (int)idx; while (map->occupied[idx]) { if (map->keys[idx] == key) return map->counts[idx]; idx = (idx + 1) % (unsigned int)map->capacity; if ((int)idx == start) break; } return 0; } void decrement(HashMap *map, int key) { unsigned int idx = hashFunc(key, map->capacity); int start = (int)idx; while (map->occupied[idx]) { if (map->keys[idx] == key) { map->counts[idx]--; return; } idx = (idx + 1) % (unsigned int)map->capacity; if ((int)idx == start) return; } } int arraysEqualHash(const int a[], int n, const int b[], int m) { if (n != m) return 0; HashMap *map = createHashMap(TABLE_SIZE); if (map == NULL) return 0; for (int i = 0; i < n; i++) increment(map, a[i]); int result = 1; for (int i = 0; i < m; i++) { int c = getCount(map, b[i]); if (c == 0) { result = 0; break; } decrement(map, b[i]); } freeHashMap(map); return result; } int main(void) { int a[] = {3, 5, 2, 5, 2}; int b[] = {2, 3, 5, 5, 2}; int n = sizeof(a) / sizeof(a[0]); int m = sizeof(b) / sizeof(b[0]); printf("%s\n", arraysEqualHash(a, n, b, m) ? "true" : "false"); return 0; }

Expected output:

text

true

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

---

Full Practical Code Example with Explanation

This program compares both approaches with verification and edge cases.

c

/** * arrays_equal.c * Checks if two arrays have the same multiset of elements. * Compares sorting and hash-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 /* 2^18 */ /* ---------- Approach 1: Sorting ---------- */ static int compareInts(const void *x, const void *y) { int a = *(const int *)x; int b = *(const int *)y; return (a > b) - (a < b); } int arraysEqualSorted(const int a_in[], int n, const int b_in[], int m) { if (n != m) return 0; if (n == 0) return 1; int *a = malloc(n * sizeof(int)); int *b = malloc(m * sizeof(int)); if (a == NULL || b == NULL) { free(a); free(b); return -1; } memcpy(a, a_in, n * sizeof(int)); memcpy(b, b_in, m * sizeof(int)); qsort(a, n, sizeof(int), compareInts); qsort(b, m, sizeof(int), compareInts); int result = 1; for (int i = 0; i < n; i++) { if (a[i] != b[i]) { result = 0; break; } } free(a); free(b); return result; } /* ---------- Approach 2: Hash Map ---------- */ typedef struct { int *keys; int *counts; int *occupied; int capacity; } HashMap; static unsigned int hashFunc(int key, int capacity) { return ((unsigned int)key) % (unsigned int)capacity; } HashMap *createHashMap(int capacity) { HashMap *map = malloc(sizeof(HashMap)); if (map == NULL) return NULL; map->keys = malloc(capacity * sizeof(int)); map->counts = calloc(capacity, sizeof(int)); map->occupied = calloc(capacity, sizeof(int)); if (map->keys == NULL || map->counts == NULL || map->occupied == NULL) { free(map->keys); free(map->counts); free(map->occupied); free(map); return NULL; } map->capacity = capacity; return map; } void freeHashMap(HashMap *map) { if (map) { free(map->keys); free(map->counts); free(map->occupied); free(map); } } void increment(HashMap *map, int key) { unsigned int idx = hashFunc(key, map->capacity); int start = (int)idx; while (map->occupied[idx]) { if (map->keys[idx] == key) { map->counts[idx]++; return; } idx = (idx + 1) % (unsigned int)map->capacity; if ((int)idx == start) return; } map->keys[idx] = key; map->counts[idx] = 1; map->occupied[idx] = 1; } int getCount(HashMap *map, int key) { unsigned int idx = hashFunc(key, map->capacity); int start = (int)idx; while (map->occupied[idx]) { if (map->keys[idx] == key) return map->counts[idx]; idx = (idx + 1) % (unsigned int)map->capacity; if ((int)idx == start) break; } return 0; } void decrement(HashMap *map, int key) { unsigned int idx = hashFunc(key, map->capacity); int start = (int)idx; while (map->occupied[idx]) { if (map->keys[idx] == key) { map->counts[idx]--; return; } idx = (idx + 1) % (unsigned int)map->capacity; if ((int)idx == start) return; } } int arraysEqualHash(const int a[], int n, const int b[], int m) { if (n != m) return 0; if (n == 0) return 1; HashMap *map = createHashMap(TABLE_SIZE); if (map == NULL) return -1; for (int i = 0; i < n; i++) increment(map, a[i]); int result = 1; for (int i = 0; i < m; i++) { int c = getCount(map, b[i]); if (c == 0) { result = 0; break; } decrement(map, b[i]); } freeHashMap(map); 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("]"); } static void demoBasic(void) { printf("\n=== Sample Arrays ===\n"); int a1[] = {1, 2, 5, 4, 0}; int b1[] = {2, 4, 5, 0, 1}; int a2[] = {1, 2, 5, 4, 0, 2, 1}; int b2[] = {2, 4, 5, 0, 1, 1, 2}; int a3[] = {1, 7, 1}; int b3[] = {7, 7, 1}; struct { int *a, *b; int n, m; } tests[] = { {a1, b1, 5, 5}, {a2, b2, 7, 7}, {a3, b3, 3, 3} }; for (int t = 0; t < 3; t++) { printf("\nTest %d:\n a = ", t + 1); printArray(tests[t].a, tests[t].n); printf("\n b = "); printArray(tests[t].b, tests[t].m); printf("\n Sorted: %s\n", arraysEqualSorted(tests[t].a, tests[t].n, tests[t].b, tests[t].m) ? "true" : "false"); printf(" Hash: %s\n", arraysEqualHash(tests[t].a, tests[t].n, tests[t].b, tests[t].m) ? "true" : "false"); } printf("\n"); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Both empty */ printf("Both empty: sorted=%s, hash=%s\n", arraysEqualSorted(NULL, 0, NULL, 0) ? "true" : "false", arraysEqualHash(NULL, 0, NULL, 0) ? "true" : "false"); /* Different lengths */ int a1[] = {1, 2, 3}; int b1[] = {1, 2}; printf("Different lengths: sorted=%s, hash=%s\n", arraysEqualSorted(a1, 3, b1, 2) ? "true" : "false", arraysEqualHash(a1, 3, b1, 2) ? "true" : "false"); /* Same single element */ int a2[] = {42}; int b2[] = {42}; printf("Single equal: sorted=%s, hash=%s\n", arraysEqualSorted(a2, 1, b2, 1) ? "true" : "false", arraysEqualHash(a2, 1, b2, 1) ? "true" : "false"); /* Different frequencies */ int a3[] = {1, 1, 2}; int b3[] = {1, 2, 2}; printf("Different frequencies: sorted=%s, hash=%s\n", arraysEqualSorted(a3, 3, b3, 3) ? "true" : "false", arraysEqualHash(a3, 3, b3, 3) ? "true" : "false"); /* Negatives */ int a4[] = {-1, -5, -1, 3}; int b4[] = {3, -1, -5, -1}; printf("Negatives: sorted=%s, hash=%s\n", arraysEqualSorted(a4, 4, b4, 4) ? "true" : "false", arraysEqualHash(a4, 4, b4, 4) ? "true" : "false"); /* Zeros */ int a5[] = {0, 0, 1}; int b5[] = {1, 0, 0}; printf("Zeros: sorted=%s, hash=%s\n", arraysEqualSorted(a5, 3, b5, 3) ? "true" : "false", arraysEqualHash(a5, 3, b5, 3) ? "true" : "false"); /* Same array identity */ int a6[] = {5, 4, 3, 2, 1}; printf("Same array: sorted=%s, hash=%s\n", arraysEqualSorted(a6, 5, a6, 5) ? "true" : "false", arraysEqualHash(a6, 5, a6, 5) ? "true" : "false"); } static void performanceTest(void) { printf("\n=== Performance Comparison (n = 100000) ===\n"); int n = 100000; int *a = malloc(n * 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 < n; i++) { a[i] = rand() % 1000; b[i] = a[i]; } /* Shuffle b */ for (int i = n - 1; i > 0; i--) { int j = rand() % (i + 1); int tmp = b[i]; b[i] = b[j]; b[j] = tmp; } clock_t start, end; double t; start = clock(); int r1 = arraysEqualSorted(a, n, b, n); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sorted: result=%s, time=%.3f ms\n", r1 ? "true" : "false", t); start = clock(); int r2 = arraysEqualHash(a, n, b, n); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash: result=%s, time=%.3f ms\n", r2 ? "true" : "false", t); printf("Verification: %s\n", (r1 == r2) ? "PASS" : "FAIL"); free(a); free(b); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Arrays Equal 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. Sorting: Copy inputs (to preserve), sort both, compare element by element.
2. Hash Map: Count occurrences in a; decrement counts using b. If any b element’s count hits 0 before decrement, arrays differ.

Expected Output (sample run)

text

=== Sample Arrays === Test 1: a = [1, 2, 5, 4, 0] b = [2, 4, 5, 0, 1] Sorted: true Hash: true Test 2: a = [1, 2, 5, 4, 0, 2, 1] b = [2, 4, 5, 0, 1, 1, 2] Sorted: true Hash: true Test 3: a = [1, 7, 1] b = [7, 7, 1] Sorted: false Hash: false === Edge Cases === Both empty: sorted=true, hash=true Different lengths: sorted=false, hash=false Single equal: sorted=true, hash=true Different frequencies: sorted=false, hash=false Negatives: sorted=true, hash=true Zeros: sorted=true, hash=true Same array: sorted=true, hash=true === Performance Comparison (n = 100000) === Sorted: result=true, time=15.234 ms Hash: result=true, time=9.876 ms Verification: PASS

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Comparing Lengths First

Different lengths → not equal. Always check n == m first.

2. Forgetting Counts

Two arrays with the same set but different counts are not equal.

c

a = [1, 1, 2]; b = [1, 2, 2]; /* Not equal */

3. Mutating Input

Sort-based approach modifies inputs unless copied.

Solution: Copy before sorting.

4. Empty Arrays

Both empty → equal. Guard against NULL arrays.

5. Hash Collisions

Ensure hash table sized appropriately; handle probe loops.

6. Negative Keys

Cast to unsigned int in hash function.

7. Early Exit

Return as soon as mismatch found.

8. Count Overflow

Use int counts; for extreme cases, int64_t.

9. Duplicate Elements

The frequency-counting approach naturally handles duplicates.

10. Memory Considerations

• Sorted: O(n) copy or O(1) in-place; O(n log n) time.
• Hash: O(n) extra space; O(n) time.
• Hash is preferred for large unsorted arrays.

---

Summary & Best Practices

Checking arrays for multiset equality is a foundational operation. Sorting is simple and memory-efficient; hashing is faster in practice.

Key Takeaways

• Arrays equal ⟺ same multiset of elements.
• Sort + compare: O(n log n) time.
• Hash + count: O(n) average time.
• Always check length first.
• Empty arrays are equal.

Best Practices

1. Check length equality first.
2. Use hashing for large arrays (O(n) average).
3. Use sorting when memory is constrained.
4. Copy inputs before sorting if preservation required.
5. Use a hash map with frequency counts (not just membership).
6. Handle negatives via unsigned cast in hash.
7. Guard against NULL and zero-length arrays.
8. Free allocated memory.
9. Test edge cases: empty, single, different counts, negatives.
10. Profile for large inputs.

By mastering multiset equality checking, you’ll gain practical insight into hash maps, sorting, and array comparison.