Frequency Counting — Who Appears Most?

Real-world analogy

What is it?

Frequency counting is the technique of counting how many times each distinct element appears in a collection of data. Using arrays (for small value ranges) or maps (for large ranges), you can quickly build a frequency table that answers questions like 'what appears most?' and 'what appears exactly once?'

Real-world relevance

Frequency counting is everywhere: word clouds show the most common words in a text, music apps track your most-played songs, websites count page views, election results count votes per candidate, and spam filters count suspicious word frequencies in emails. Any time you see 'most popular' or 'top 10,' frequency counting is behind it.

Key points

• What is Frequency Counting? — Frequency counting means figuring out how many times each element appears in a collection. Given [1, 3, 2, 1, 3, 1], the frequencies are: 1 appears 3 times, 2 appears 1 time, 3 appears 2 times. This is one of the most common patterns in CP!
• Using an Array as a Counter — If values range from 0 to some max value, use a simple array: int freq[MAX] = {0}; Then for each element x, do freq[x]++. This is O(1) per element — super fast! Works great when values are small (like 0 to 1000).
• Using map for Large Ranges — If values can be huge (like up to 10^9), an array would waste too much memory. Instead, use map freq; and do freq[x]++. A map only stores entries for values that actually appear. Each operation is O(log n).
• Finding the Most Frequent Element — After counting frequencies, loop through your frequency data to find the maximum count. Keep track of which element has the highest frequency. If there is a tie, the problem will usually specify which one to pick (first occurrence, smallest value, etc.).
• Finding the Least Frequent Element — Similarly, you can find elements that appear only once (unique elements) or the least frequent element. These are common in problems like 'find the unique number' or 'find the element that appears an odd number of times.'
• Counting Characters in Strings — For strings, you can count character frequencies using an array of size 26 (for lowercase letters): freq[s[i] - 'a']++. The expression s[i] - 'a' converts a letter to a number: 'a' becomes 0, 'b' becomes 1, ..., 'z' becomes 25.
• Frequency Counting Applications — Frequency counting is used in: checking if two strings are anagrams, finding duplicate elements, computing histograms, solving problems about majorities, and many string manipulation problems. It is a fundamental building block.
• unordered_map for Speed — If you need map-like behavior but faster, use unordered_map. It uses a hash table for O(1) average operations instead of map's O(log n). However, in CP, unordered_map can sometimes be slow due to hash collisions, so use it carefully.

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Method 1: Array-based frequency counting
    int n;
    cin >> n;
    vector<int> arr(n);
    int freq[1001] = {0}; // Values 0 to 1000

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        freq[arr[i]]++;
    }

    // Find most frequent element
    int maxFreq = 0, mostCommon = 0;
    for (int i = 0; i <= 1000; i++) {
        if (freq[i] > maxFreq) {
            maxFreq = freq[i];
            mostCommon = i;
        }
    }
    cout << "Most common: " << mostCommon << " (appears " << maxFreq << " times)\n";

    // Method 2: Map-based frequency counting
    map<int, int> freqMap;
    for (int i = 0; i < n; i++) {
        freqMap[arr[i]]++;
    }
    cout << "Distinct elements: " << freqMap.size() << "\n";
    for (auto& p : freqMap) {
        cout << p.first << " -> " << p.second << " times\n";
    }

    // Character frequency in a string
    string s = "hello";
    int charFreq[26] = {0};
    for (char c : s) charFreq[c - 'a']++;
    for (int i = 0; i < 26; i++) {
        if (charFreq[i] > 0) {
            cout << (char)('a' + i) << ": " << charFreq[i] << "\n";
        }
    }

    return 0;
}

Line-by-line walkthrough

1. 1. int freq[1001] = {0}; — we create an array of 1001 zeros (for values 0 through 1000). Each position freq[x] will count how many times the number x appears. Initializing to 0 is important!
2. 2. freq[arr[i]]++; — for each element arr[i], we increment its count. If arr[i] is 5, then freq[5] goes up by 1. After processing all elements, freq[5] tells us how many times 5 appeared.
3. 3. if (freq[i] > maxFreq) — we scan through all possible values to find which one has the highest count. This finds the most frequent element.
4. 4. map freqMap; freqMap[arr[i]]++; — a map works like our frequency array but handles any integer value, not just 0-1000. It only stores entries for values that actually exist.
5. 5. freqMap.size() — returns the number of distinct elements. Since map only creates entries for values we have seen, its size equals the count of unique values.
6. 6. charFreq[c - 'a']++; — for a character c, subtracting 'a' gives its position in the alphabet (a=0, b=1, ..., z=25). This lets us use a small array of size 26 to count all lowercase letters.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    int freq[100] = {0};

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        freq[arr[i]]++;
    }

    int maxFreq = 0, answer = 0;
    for (int i = 0; i < 100; i++) {
        if (freq[i] > maxFreq) {
            maxFreq = freq[i];
            answer = i;
        }
    }
    cout << "Most frequent: " << answer << "\n";
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Frequency Counting Techniques (GeeksforGeeks)
• Hashing and Frequency Arrays (YouTube)
• Two Sets Problem (CSES)