Most Frequent Element in Array in C: Complete Guide

Most Frequent Element in an Array in C: A Comprehensive Tutorial

Finding the most frequent element in an array is a foundational problem that tests your understanding of frequency counting, tie-breaking rules, and time–space trade-offs. With the requirement to return the largest value in case of ties, this problem also reinforces comparison logic and careful edge-case handling.

This tutorial provides an in-depth exploration of three approaches in C: naive nested loops, sort-and-scan, and optimal hash-map counting. Complete, portable C99/C11 code examples are provided for each.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Given an integer array arr[], find the element that appears most frequently. If multiple elements share the highest frequency, return the largest value among them.

Examples:

text

Input: [1, 3, 2, 1, 4, 1] Output: 1 (1 appears three times) Input: [10, 20, 10, 20, 30, 20, 20] Output: 20 (20 appears four times) Input: [1, 2, 2, 4, 1] Output: 2 (1 and 2 tie at 2; return larger)

Why This Problem Matters

• Frequency counting: Core of histograms, mode calculation, and voting systems.
• Tie-breaking logic: Reinforces comparison and update rules.
• Algorithm comparison: O(n²), O(n log n), O(n) trade-offs.
• Interview preparation: Common coding interview question.
• Real-world use: Analytics, log analysis, election results.

Approaches Overview

Approach	Time Complexity	Space Complexity
Naive nested loops	O(n²)	O(1)
Sorting	O(n log n)	O(1) or O(n)
Hash map	O(n) average	O(n)

The Tie-Breaking Rule

Whenever frequencies are equal, keep the larger value:

c

if (cnt > maxCnt || (cnt == maxCnt && val > res)) { res = val; maxCnt = cnt; }

---

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

Count occurrences of each element by scanning the entire array.

c

#include <stdio.h> #include <limits.h> int mostFreqNaive(const int arr[], int n) { if (n <= 0) return INT_MIN; int maxCnt = 0; int res = arr[0]; for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j < n; j++) { if (arr[i] == arr[j]) cnt++; } if (cnt > maxCnt || (cnt == maxCnt && arr[i] > res)) { maxCnt = cnt; res = arr[i]; } } return res; } int main(void) { int arr[] = {40, 50, 30, 40, 50, 30, 30}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", mostFreqNaive(arr, n)); return 0; }

Expected output:

text

30

Time: O(n²), Space: O(1)

Approach 2: Sorting + Linear Scan

After sorting, equal elements are adjacent. Track run lengths and apply tie-break.

c

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> static int compareInts(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); } int mostFreqSorted(const int arr_in[], int n) { if (n <= 0) return INT_MIN; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return INT_MIN; memcpy(arr, arr_in, (size_t)n * sizeof(int)); qsort(arr, n, sizeof(int), compareInts); int maxCnt = 1; int res = arr[0]; int currCnt = 1; for (int i = 1; i < n; i++) { if (arr[i] == arr[i - 1]) currCnt++; else currCnt = 1; if (currCnt > maxCnt || (currCnt == maxCnt && arr[i] > res)) { maxCnt = currCnt; res = arr[i]; } } free(arr); return res; } int main(void) { int arr[] = {40, 50, 30, 40, 50, 30, 30}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", mostFreqSorted(arr, n)); return 0; }

Expected output:

text

30

Time: O(n log n), Space: O(n) if copied; O(1) if in-place mutation is acceptable

Approach 3: Hash Map (Optimal)

Count frequencies in one pass, then find the maximum with tie-break.

c

#include <stdio.h> #include <stdlib.h> #include <limits.h> #define TABLE_SIZE 16384 typedef struct { int *keys; int *counts; int *occupied; int capacity; int size; } 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; m->size = 0; 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; /* Table full */ } m->keys[idx] = key; m->counts[idx] = 1; m->occupied[idx] = 1; m->size++; } int mostFreqHash(const int arr[], int n) { if (n <= 0) return INT_MIN; FreqMap *m = createMap(TABLE_SIZE); if (m == NULL) return INT_MIN; for (int i = 0; i < n; i++) increment(m, arr[i]); int maxCnt = 0; int res = INT_MIN; for (int i = 0; i < m->capacity; i++) { if (!m->occupied[i]) continue; int val = m->keys[i]; int cnt = m->counts[i]; if (cnt > maxCnt || (cnt == maxCnt && val > res)) { maxCnt = cnt; res = val; } } freeMap(m); return res; } int main(void) { int arr[] = {40, 50, 30, 40, 50, 30, 30}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", mostFreqHash(arr, n)); return 0; }

Expected output:

text

30

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

---

Full Practical Code Example with Explanation

This program compares all three approaches, verifies their equality, and exercises edge cases.

c

/** * most_frequent.c * Finds the most frequent element in an array; ties broken by larger value. * Compares naive, sorting, and hash map approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <limits.h> #include <time.h> #define MAX_LINE_LEN 100 #define TABLE_SIZE 262144 /* 2^18 */ /* ============================================================ * Approach 1: Naive nested loops * ============================================================ */ int mostFreqNaive(const int arr[], int n) { if (n <= 0) return INT_MIN; int maxCnt = 0; int res = arr[0]; for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j < n; j++) { if (arr[i] == arr[j]) cnt++; } if (cnt > maxCnt || (cnt == maxCnt && arr[i] > res)) { maxCnt = cnt; res = arr[i]; } } return res; } /* ============================================================ * Approach 2: Sorting * ============================================================ */ static int compareInts(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); } int mostFreqSorted(const int arr_in[], int n) { if (n <= 0) return INT_MIN; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return INT_MIN; memcpy(arr, arr_in, (size_t)n * sizeof(int)); qsort(arr, n, sizeof(int), compareInts); int maxCnt = 1; int res = arr[0]; int currCnt = 1; for (int i = 1; i < n; i++) { if (arr[i] == arr[i - 1]) currCnt++; else currCnt = 1; if (currCnt > maxCnt || (currCnt == maxCnt && arr[i] > res)) { maxCnt = currCnt; res = arr[i]; } } free(arr); return res; } /* ============================================================ * Approach 3: Hash map * ============================================================ */ typedef struct { int *keys; int *counts; int *occupied; int capacity; int size; } 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; m->size = 0; 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; m->size++; } int mostFreqHash(const int arr[], int n) { if (n <= 0) return INT_MIN; FreqMap *m = createMap(TABLE_SIZE); if (m == NULL) return INT_MIN; for (int i = 0; i < n; i++) increment(m, arr[i]); int maxCnt = 0; int res = INT_MIN; for (int i = 0; i < m->capacity; i++) { if (!m->occupied[i]) continue; int val = m->keys[i]; int cnt = m->counts[i]; if (cnt > maxCnt || (cnt == maxCnt && val > res)) { maxCnt = cnt; res = val; } } freeMap(m); 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 arr1[] = {1, 3, 2, 1, 4, 1}; int arr2[] = {10, 20, 10, 20, 30, 20, 20}; int arr3[] = {1, 2, 2, 4, 1}; int arr4[] = {40, 50, 30, 40, 50, 30, 30}; struct { int *arr; int n; } tests[] = { {arr1, 6}, {arr2, 7}, {arr3, 5}, {arr4, 7} }; int nt = sizeof(tests) / sizeof(tests[0]); for (int t = 0; t < nt; t++) { printf("\nTest %d: ", t + 1); printArray(tests[t].arr, tests[t].n); int a = mostFreqNaive(tests[t].arr, tests[t].n); int b = mostFreqSorted(tests[t].arr, tests[t].n); int c = mostFreqHash(tests[t].arr, tests[t].n); printf("\n Naive: %d\n Sorted: %d\n Hash: %d\n", a, b, c); printf(" Verify: %s\n", (a == b && b == c) ? "PASS" : "FAIL"); } printf("\n"); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Empty array */ printf("Empty array: naive=%d, sorted=%d, hash=%d\n", mostFreqNaive(NULL, 0), mostFreqSorted(NULL, 0), mostFreqHash(NULL, 0)); /* Single element */ int a1[] = {42}; printf("Single element: %d / %d / %d\n", mostFreqNaive(a1, 1), mostFreqSorted(a1, 1), mostFreqHash(a1, 1)); /* All distinct */ int a2[] = {1, 2, 3, 4, 5}; printf("All distinct: %d / %d / %d (each freq=1 → largest=5)\n", mostFreqNaive(a2, 5), mostFreqSorted(a2, 5), mostFreqHash(a2, 5)); /* All same */ int a3[] = {7, 7, 7, 7}; printf("All same: %d / %d / %d\n", mostFreqNaive(a3, 4), mostFreqSorted(a3, 4), mostFreqHash(a3, 4)); /* Tie between two values */ int a4[] = {1, 2, 2, 4, 1}; printf("Tie 1 & 2: %d / %d / %d (expect 2)\n", mostFreqNaive(a4, 5), mostFreqSorted(a4, 5), mostFreqHash(a4, 5)); /* Tie between negatives */ int a5[] = {-5, -5, -2, -2, 0}; printf("Tie -5 & -2: %d / %d / %d (expect -2)\n", mostFreqNaive(a5, 5), mostFreqSorted(a5, 5), mostFreqHash(a5, 5)); /* Zero and positives tie */ int a6[] = {0, 0, 3, 3, 3, 0}; printf("Tie 0 & 3: %d / %d / %d (expect 3)\n", mostFreqNaive(a6, 6), mostFreqSorted(a6, 6), mostFreqHash(a6, 6)); /* All negatives */ int a7[] = {-1, -2, -3, -2, -1, -1}; printf("All negatives: %d / %d / %d (expect -1)\n", mostFreqNaive(a7, 6), mostFreqSorted(a7, 6), mostFreqHash(a7, 6)); /* Multiple ties */ int a8[] = {5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2}; printf("Multi-tie: %d / %d / %d (expect 5)\n", mostFreqNaive(a8, 12), mostFreqSorted(a8, 12), mostFreqHash(a8, 12)); } static void performanceTest(void) { printf("\n=== Performance Comparison ===\n"); /* Naive: keep small */ int smallN = 3000; int *sa = malloc((size_t)smallN * sizeof(int)); if (sa == NULL) return; srand(42); for (int i = 0; i < smallN; i++) sa[i] = rand() % 500; clock_t start, end; double t; start = clock(); int r1 = mostFreqNaive(sa, smallN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (n=%d): result=%d, time=%.3f ms\n", smallN, r1, t); start = clock(); int r2 = mostFreqSorted(sa, smallN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sorted (n=%d): result=%d, time=%.3f ms\n", smallN, r2, t); start = clock(); int r3 = mostFreqHash(sa, smallN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=%d): result=%d, time=%.3f ms\n", smallN, r3, t); printf("Verify: %s\n", (r1 == r2 && r2 == r3) ? "PASS" : "FAIL"); free(sa); /* Large: hash only */ int largeN = 5000000; int *la = malloc((size_t)largeN * sizeof(int)); if (la == NULL) return; for (int i = 0; i < largeN; i++) la[i] = rand() % 100000; start = clock(); int r4 = mostFreqHash(la, largeN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=%d): result=%d, time=%.3f ms\n", largeN, r4, t); free(la); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Most Frequent Element 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, count occurrences in a nested loop. Simple but quadratic.
2. Sorted: Sort, then scan runs. Efficient for moderate sizes; uses O(n) memory unless in-place is acceptable.
3. Hash: One pass to count, one pass to find max. Optimal for large inputs.

Expected Output (sample run)

text

=== Sample Arrays === Test 1: [1, 3, 2, 1, 4, 1] Naive: 1 Sorted: 1 Hash: 1 Verify: PASS Test 2: [10, 20, 10, 20, 30, 20, 20] Naive: 20 Sorted: 20 Hash: 20 Verify: PASS Test 3: [1, 2, 2, 4, 1] Naive: 2 Sorted: 2 Hash: 2 Verify: PASS Test 4: [40, 50, 30, 40, 50, 30, 30] Naive: 30 Sorted: 30 Hash: 30 Verify: PASS === Edge Cases === Empty array: naive=-2147483648, sorted=-2147483648, hash=-2147483648 Single element: 42 / 42 / 42 All distinct: 5 / 5 / 5 (each freq=1 → largest=5) All same: 7 / 7 / 7 Tie 1 & 2: 2 / 2 / 2 (expect 2) Tie -5 & -2: -2 / -2 / -2 (expect -2) Tie 0 & 3: 3 / 3 / 3 (expect 3) All negatives: -1 / -1 / -1 (expect -1) Multi-tie: 5 / 5 / 5 (expect 5) === Performance Comparison === Naive (n=3000): result=?, time=~180 ms Sorted (n=3000): result=?, time=~1 ms Hash (n=3000): result=?, time=~0.5 ms Verify: PASS Hash (n=5000000): result=?, time=~280 ms

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Tie-Breaking Rule Reversed

The problem specifies “return the largest” among tied elements. Reversing this is a common error.

c

if (cnt > maxCnt || (cnt == maxCnt && val > res)) /* Correct */

2. Uninitialized res

If res starts as arr[0] but the first element is not the maximum in a tie, correctness depends on the update rule. Initialize res to arr[0] and apply the tie-break consistently.

3. Empty Array

Return a sentinel (INT_MIN). Document the behavior in your API.

4. Integer Overflow

Counts fit in int for arrays smaller than INT_MAX. Use size_t for very large arrays.

5. Hash Table Sizing

Table must be ≥ 2× number of distinct elements. Undersized → probe failures.

6. Negative Values

Cast to unsigned int in the hash function.

7. All Distinct

Every element has count 1 → tie → returns the maximum.

8. All Same

Every element has count n → returns that value.

9. Mutating Input in Sorted Approach

Copy first if the caller expects inputs preserved.

10. Memory Considerations

• Naive: O(1) extra space.
• Sorted: O(n) for copy; O(n log n) time.
• Hash: O(n) extra space; O(n) time.
• Free all dynamic allocations.

---

Summary & Best Practices

Finding the most frequent element with a largest-value tie-break is a classic problem. The hash-map approach is optimal for large inputs; sorting works well when memory is constrained; naive is only for tiny arrays.

Key Takeaways

• Count frequencies, then find the max with tie-break.
• Naive: O(n²) — educational only.
• Sorted: O(n log n) — moderate sizes.
• Hash: O(n) average — preferred.
• Tie-break: choose the larger value.
• Empty arrays: return a documented sentinel.

Best Practices

1. Use a hash map for O(n) average performance.
2. Apply the tie-break consistently (cnt > maxCnt || (cnt == maxCnt && val > res)).
3. Initialize res carefully to avoid unintended behavior in ties.
4. Handle empty arrays gracefully.
5. Size hash tables ≥ 2× distinct elements.
6. Cast negative keys to unsigned int.
7. Copy inputs before sorting if preservation needed.
8. Free allocated memory.
9. Test edge cases: empty, single, all-same, all-distinct, ties, negatives.
10. Profile for large inputs.

By mastering frequency counting and tie-breaking, you’ll be prepared for histogram analysis, voting systems, and a wide class of statistics-oriented problems.