How frequency array works and created
A frequency array stores how many times each value appears. If we have an array and many questions like “how many times does value appear?”, we can first count all values once and then answer each question directly.
For example, in the array , the value appears times, the value appears times, and the value appears time. A frequency array keeps exactly this information.
We use this idea in problems where values must be counted: counting equal numbers, checking whether a value appeared, finding a frequent value, comparing letter counts in strings, or answering many occurrence queries.
Suppose we are given an array of integers. Every value is between and . Then we are given queries. Each query gives a number , and we must print how many times appears in the array.
Example array: .
Queries:
The important detail is that there can be many queries. If we scan the whole array for every query, we repeat the same counting work many times.
A direct way is to handle each query separately. For a query , we go through the whole array and count how many elements are equal to .
This gives the correct answer because every position is checked. The problem is the running time. If and , then this approach may do about checks, which is too slow.
This code is fine when we only have one query. It is not good when the same type of query is asked many times.
The idea is to count once and reuse the result. We create an array . The index is the value, and the stored number is the frequency of that value. So means value appeared times.
When we read an element , we increase by . We are saying: “we found one more occurrence of this value.” After all elements are processed, already contains the answer for value .
The invariant is:
After reading the first elements, stores how many times value appeared among those first elements.
This works when values can be used as array indices. Values up to are usually fine. If values are very large, negative, or strings, then we normally use a map, an unordered map, or coordinate compression.
First, all frequencies are zero. Then we read the array from left to right. For every value , we increase . After this preprocessing step, each query is answered by printing .
Algorithm:
int answer = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == x) {
answer++;
}
}
cout << answer << '\n';
1. Read n and q.
2. Create cnt filled with zeroes.
3. For i = 1 to n:
3.1. Read x.
3.2. Increase cnt[x] by 1.
4. Repeat q times:
4.1. Read x.
4.2. Print cnt[x].
#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
const int V = 1000100;
int n, q;
int a[N];
int cnt[V];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
cnt[a[i]]++;
}
while (q--) {
int x;
cin >> x;
cout << cnt[x] << '\n';
}
return 0;
}