Frequency Array

Basic Frequency Count

Count how many times each value appears in an array:

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

freq[v] = how many times v appears.

This is O(n) and works when values are bounded (e.g. 1 ≤ x ≤ n).

Problems using this

• D. Spy Detected! — find the element that appears once (others appear twice)

First Element Appearing K Times

Scan the array while incrementing frequency. Return the first value that reaches frequency k:

int freq[n + 1] = {};
int ans = -1;
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    freq[x]++;
    if (freq[x] >= 3) ans = x;
}
cout << ans;

We don’t stop early — we want the first element to reach 3 occurrences (in order of appearance).

Problems using this

• A. Triple — first element appearing 3 times

Pangram Check

Check if a string contains every letter at least once:

int freq[26] = {};
for (int i = 0; i < n; i++) {
    freq[tolower(s[i]) - 'a']++;
}
for (int i = 0; i < 26; i++) {
    if (freq[i] == 0) { cout << "NO"; return; }
}
cout << "YES";

Problems using this

• F. Pangram

Frequency in Sliding Window

Track distinct element count inside a sliding window — used heavily in two-pointer problems.

vi freq(100005, 0);
ll cnt = 0;   // number of distinct elements
for (ll r = 0; r < n; r++) {
    if (freq[arr[r]] == 0) cnt++;
    freq[arr[r]]++;
    while (cnt > k) {
        freq[arr[l]]--;
        if (freq[arr[l]] == 0) cnt--;
        l++;
    }
}

cnt tracks distinct elements. Increment when adding a new value, decrement when removing the last occurrence.

See also: Two Pointers notes — Segments with Small Set.

Problems using this

• E. Segments with Small Set (Two Pointers)
• G. Nezzar and Colorful Balls

Frequency for String / Character Counting

Same idea on characters instead of numbers:

int freq[26] = {};
for (char c : s) freq[c - 'a']++;

Useful for:

• Checking if two strings are anagrams
• Finding missing/extra characters
• Pangram / alphabet coverage problems

Problems using this

• F. Pangram
• B. Garland — check if rearrangement is possible

When to Use Frequency Array vs Map

// array — fast, bounded keys
int freq[100005] = {};

// map — any key type
map<ll, ll> freq;
unordered_map<string, int> mp;