Counts, ties, and groups
Build frequency maps, resolve ties, and preserve occurrence positions.
Let every arrival update one count
++frequency[x] intentionally creates a zero count when needed and then increments it. After any input prefix, each stored value equals exactly that key’s occurrences in that prefix. Map size counts distinct keys; summing mapped counts counts observations.
To choose the smallest most-frequent key, traverse an ascending map and update the candidate only for a strictly greater count. Using >= replaces earlier tied keys and leaves the largest tied key. For nonempty input, initialize bestCount to zero so a real positive count can win.
Attach an entire sequence to a key
std::map<int, std::vector<int>> can collect occurrence positions. positions[x].push_back(i) creates an empty vector for a new key and appends the current one-based input position. The map sorts groups by key; each vector keeps insertion order, so positions stay increasing when input is read left to right.
If group sizes sum to n, printing all groups visits n positions in total. The nested output loops are O(n + d), not automatically quadratic. Construction is O(n log(n + 1)) and storage includes all vectors: O(n + d). Read entries by const reference to avoid copying those vectors.
// Complete C++23 program. Input: n, followed by n integers.
#include <iostream>
#include <map>
#include <vector>
int main() {
int n;
std::cin >> n;
std::map<int, std::vector<int>> positions;
for (int i = 1; i <= n; ++i) {
int x;
std::cin >> x;
positions[x].push_back(i);
}
for (const auto& [value, indices] : positions) {
std::cout << value << ' ' << indices.size();
for (int index : indices) std::cout << ' ' << index;
std::cout << '\n';
}
}Ordering is always about the key
For a map of start time → room, lower_bound(time) finds the first starting time at least the threshold. It does not find a room number at least the threshold. Read it->first and it->second only after checking end().
Comparing two maps with == compares their stored key–value entries and can inspect all entries. String comparisons also have character cost: with maximum key length L, a conservative ordered lookup bound is O(L log(d + 1)). O(log d) assumes bounded-cost keys.
Word frequency map
Split on whitespace. Keys are case-sensitive; punctuation stays attached. Displayed in sorted key order like std::map<string, int>.
code3learn2solve16 words · 3 distinct keys
Guided simulation · Change the inputs to test your understanding.
Values 8, 3, 8, 3, 2, 2, 9 are counted. An ascending map scan replaces the best only when count > bestCount. Which key wins?
Turn the idea into code
Build the position groups for 4, 2, 4, 7, 2, 4. Explain the total number of position visits during output.
Give me a hint
Every original position belongs to one group only.
Show the explained solution
2 → [2, 5], 4 → [1, 3, 6], 7 → [4]. The groups print in key order, while positions within each group retain input order. Output visits six positions, even though the loops are nested.
Your notes
Mark complete when you can explain it yourself.