Count values with direct indexing
Size the domain, handle signed keys with offsets, and find a mode.
The index now represents a value
An ordinary sequence stores a[position] = value. A frequency table stores freq[value] = occurrence count. For [3, 0, 3, 5, 1, 3], the counts over values 0 through 5 are [1, 1, 0, 3, 0, 1]. freq[3] describes how often 3 occurs, not the third input position.
For a guaranteed domain [0, U], allocate U + 1 zero entries. The domain controls size, even when only a few observations arrive. Initialization costs O(U + 1), input costs O(n), and q exact queries cost O(q), giving O(U + n + q + 1) time and O(U + 1) storage.
Offsets translate a bounded domain
For known values from LOW through HIGH, use index = value − LOW and allocate HIGH − LOW + 1 entries. For [−1000, 1000], −1000 maps to 0 and 1000 to 2000. Apply the same mapping during both insertion and lookup.
An offset does not shrink a huge domain. Shifting [−10⁹, 10⁹] still needs over two billion entries. Use a map or compression for sparse large values. abs(value), modulo, and clamping are not general index fixes: they merge different values. Validate out-of-domain application input before indexing.
Distinct counts and tie-breaking
Count positive frequency entries to get the number of distinct values. To report the smallest mode, scan values in ascending order and update only for a strictly greater frequency. A nonempty input guarantees some positive count replaces an initially absent candidate.
Frequency tables forget arrangement. They can print values in sorted order, but they cannot reconstruct the original order or identify the first unique input occurrence unless that order is preserved separately.
// Complete C++23 program. Input: n upper, n values in [0,upper]; n >= 1.
#include <iostream>
#include <vector>
int main() {
int n, upper;
std::cin >> n >> upper;
std::vector<int> freq(upper + 1, 0);
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
++freq[x];
}
int distinct = 0, best = 0;
for (int x = 0; x <= upper; ++x) {
if (freq[x] > 0) ++distinct;
if (freq[x] > freq[best]) best = x;
}
std::cout << distinct << '\n';
std::cout << best << ' ' << freq[best] << '\n';
}Frequency array
The value becomes an index. Each arrival increases freq[value] by one. This domain has ten possible values.
Input values
freq[value] — indices are values
The frequencies add up to 6, the number of input values.
Guided simulation · Change the inputs to test your understanding.
Five inputs may range from 0 through 100. How large must a direct frequency vector be?
Turn the idea into code
For domain [−3, 3], give the allocated size and indices for −3, 0, 3. Explain why using abs(x) would be wrong.
Give me a hint
Use x − LOW with LOW = −3.
Show the explained solution
Allocate 7 entries. The values map to indices 0, 3, and 6. Taking absolute values would merge −3 and 3, even though the task counts them as different values.
Your notes
Mark complete when you can explain it yourself.