CP01: Arrays, loops, and the frequency map

Prerequisites and observable goals#

Level: Algorithms Lane, Module 1 of 14. About 8 hours: six 75-minute sessions and a shorter seventh for the gate. The clang++ compiler (Visual Studio’s on Windows), C++20, standard library only.

Warm-up: spaced review (10 minutes, closed book)#

These three target mistakes beginners commonly make before this module. Answer from memory, then check at the end of this chapter’s solutions. From CP02 on, the warm-up comes from due entries in your own error log (CP00, section E).

1. In std::unordered_map<std::string, PlayerProfile> m;, what is the key type, what is the value type, and what goes inside m[...]?
2. A first largest started with int Largest = 0;. On {-3, -1, -2} it returned $0$. What should it start from, and why?
3. Which line compiles, and why: int v = 1; v.size(); or std::vector<int> v = {4, 1, 7}; v.size();?

Number 1 returns in section 2.1 and the code-reading drill, number 2 in section 2.2, and number 3 is the first habit of this module: read the type before you use the name.

1. Quick summary#

Picture CP01.1. A loop is a cursor with a promise. The cursor visits one value per pass, and best keeps a promise: it is the largest value visited so far. Starting from v[0] (aqua), the promise is true before the first pass and stays true after every one. Starting from $0$ (orange), it is false before the loop begins, and with all-negative values no pass ever repairs it. That is warm-up question 2’s bug, drawn.

Five ideas carry this module.

1. Read the types first. A function’s signature is its plan: what comes in, and what type must come out. The return type tells you what to build.
2. A loop keeps a promise. Write one sentence that is true after every pass (the invariant), and make sure it is already true before the first pass.
3. A frequency map counts anything. counts[x]++ works even the first time x appears, because a missing key starts at zero.
4. Remember what you have seen. Storing past values in a map turns “check every pair” into “look up the partner”: memory traded for time.
5. Count the work, then measure it. Checking every pair grows like $n^2$; one pass grows like $n$. At $100{,}000$ values that is about five billion pair checks against a hundred thousand look-ups.

What you will build. About 75 lines of C++ in drills.h, in the companion code’s cp/cp01 folder: nine functions, from counting positives to counting pairs that sum to a target, tested by the 64 checks in check.cpp; a failing check prints what your code returned. A benchmark (.\run.ps1 -Bench) then times your one-pass code against the brute force, and the mastery gate (.\run.ps1 -Gate) checks three problems you have not seen. The Counting Explorer, on the companion website at bezhig.com/book/explorers/cp01-counting.html, lets you step through a loop’s promise, the tally board, a tie, and two-sum’s check-then-store, and race every-pair against one pass in your browser.

2. Deep explanation#

2.1. Read the types first#

Every name in C++ has a type, and the type decides what you may do with the name. Before using any name, say its type card aloud: what it holds, and what it can do.

A map’s type names two types, in order: std::unordered_map<Key, Value>. The key is what goes inside the brackets of m[...]; the value is what comes back. In warm-up question 1, the key is a std::string, such as a player’s ID, and the value a PlayerProfile record. In code someone else wrote, the way to know is to open the declaration, never to guess from a nearby name.

The signature is the plan. Read

std::unordered_map<int, int> countEach(const std::vector<int>& v)

from right to left: it takes a read-only view of a vector of ints (const&, so nothing is copied) and returns a map from int to int. So the body must create a map, fill it, and return it. A common first attempt reaches for one int counter, but the return type has already said that a single number cannot be the answer.

2.2. Loops that keep a promise#

Most loops in this module are accumulators: a variable that collects an answer as a cursor visits each value. The trick to writing them correctly is to write their promise first, one sentence that is true after every pass:

• total: “total is the sum of the values visited so far.” Before any visit that sum is $0$, so start at $0$.
• count: “count is the number of visited values that pass the test.” Start at $0$.
• best: “best is the largest value visited so far.” Before any visit there is no largest value. Make the promise true by starting from a real value, v[0], which needs v to be non-empty (the contract for largest guarantees it).

Each pass keeps the promise: if it was true before the pass, it is true after. When the loop ends, every value has been visited, so the promise is the answer. That is the whole proof of correctness, and Picture CP01.1 shows what happens when the starting value breaks it.

Two ways to walk a vector. The range loop for (int x : v) hands you each value; use it when you only need values. The index loop for (int i = 0; i < static_cast<int>(v.size()); ++i) hands you positions; use it when the answer is a position, as in firstUnique and twoSum. v.size() has the type std::size_t, an unsigned whole number, one that can never be negative. Comparing it with a signed int makes the compiler warn (-Wsign-compare), because a negative int would be read as a huge unsigned number. The cure is static_cast<int>(v.size()): static_cast<T>(x) means “convert x to the type T, on purpose and in plain sight”. Make it a habit.

2.3. The frequency map#

Picture CP01.2. A frequency map is a tally board. Four visits over {3, 1, 3, 3}. When the key is new (yellow), counts[x] first creates it with count $0$ and the ++ makes it $1$; when the key exists (aqua), ++ adds one to its tally. After the last visit the board answers “how many of each?” for every value at once.

A frequency map is an std::unordered_map<Value, int> from each value to how many times it has appeared. One line fills it:

std::unordered_map<int, int> counts;
for (int x : v) counts[x]++;   // promise: counts holds the tally of every value visited

Why does counts[x]++ work the first time? Because operator[] on a map that lacks the key inserts it with a default value, which for int is $0$, and then the ++ adds one. That same behaviour is a trap when you only want to look: counts[4] on a map without $4$ quietly adds the key $4$ with count $0$. To ask “is it there?” without changing the map, use counts.count(4) (which returns $0$ or $1$) or counts.find(4).

Order is not a property of the map. Looping over an unordered_map visits its pairs in an order the standard leaves unspecified. It can change between compilers, between runs of a program that inserts differently, and as the map grows. So a rule like “break ties by the smaller value” must be written into your code; it never comes for free from the map. If you need keys in sorted order, std::map keeps them sorted, at the cost of $\log n$ work per operation instead of the hash map’s typical constant.

When a plain array beats a map. If the values are small and known in advance, like the 26 lowercase letters, an array of counts does the same job faster: int counts[26] = {}; then counts[c - 'a']++. That relies on 'a' to 'z' being consecutive codes, which holds in ASCII and UTF-8, the encodings you will use.

2.4. Remember what you have seen: two-sum#

Picture CP01.3. Two ways to find a pair that sums to $9$ in {2, 7, 11, 15}. Left: try every pair $i<j$ (the shaded upper triangle); the work grows like $n^2$. Right: walk once, and for each value look up the partner it needs among the values already seen; the work grows like $n$.

The two-sum problem asks for two positions whose values add to a target. Checking every pair is correct but slow. The fast idea is a promise about memory: “indexOf maps every value visited so far to a position where it appeared.” At position $j$, the partner value $v[j]$ needs is $\text{target}-v[j]$; one look-up says whether it has been seen. Then store $v[j]$ and move on.

Check before you store. The order of those two moves is the whole subtlety. If you store $v[j]$ first and then look for its partner, a value can find itself: with {3, 2, 4} and target $6$, position $0$ would pair $3$ with its own copy and return {0, 0}. Checking first means the memory only ever holds earlier positions, so a found partner is always at an index $i<j$. Section 3.7 asks you to break this on purpose and watch which check catches it.

Counting pairs instead of finding one. Step 9 asks how many pairs sum to the target. The same memory now holds how many times each value has been seen. At position $j$, every earlier copy of the partner makes one new pair, so add that count, then record $v[j]$. With {3, 3, 3, 3} and target $6$, the running total goes $0, 1, 3, 6$: each new $3$ pairs with every $3$ before it.

2.5. Counting the work#

Before timing anything, estimate it. Checking every pair of $n$ values does about $n(n-1)/2\approx n^2/2$ steps; one pass does about $n$ steps, each a map operation costing more than a single addition but a fixed amount on average. A rough rule for planning: a modern core does on the order of $10^8$ to $10^9$ simple steps per second.

We describe this growth with big-O notation: the brute force is $O(n^2)$ (multiply $n$ by $10$ and the work grows about $100$ times), the one-pass version $O(n)$ on average (the work grows about $10$ times). A hash map’s look-up is constant time on average; with an adversarial input that makes many keys collide it can degrade, which competitive programmers occasionally defend against, but you can rely on the average in this lane. Lab step 10 measures all of this on your own machine.

When the machine beats the rule. The $10^8$ to $10^9$ rule is for planning, not a law. An optimizing compiler can turn a simple pair loop into vector instructions that test several pairs at once. On a recent desktop PC, the one this lab’s timing check was calibrated on, a brute-force pair count built by run.ps1 checked roughly $8\times10^9$ pairs per second, so $100{,}000$ values took about half a second to a second. That is why step 9’s last check uses $300{,}000$ values: there the brute force takes five to eight seconds, while one pass still takes a few milliseconds. Estimate first, then measure.

2.6. The C++ this module uses#

2.7. Beginner bugs: a field guide#

Each of these is something a careful beginner really writes. For each, the symptom you see, how to spot it in the code, and the check in check.cpp that catches it.

2.8. Design trade-offs#

• Hash map, sorted map, or array? An unordered_map is the general tool: any key, constant time on average, no order. A std::map keeps keys sorted for $O(\log n)$ per operation. A plain array is fastest of all when keys are small integers known in advance.
• Memory for time. Every fast solution here spends memory proportional to $n$ to avoid $n^2$ work. When memory is the scarce resource, sorting first (CP03) often gives $O(n\log n)$ time with no extra map.
• Two passes are still linear. firstUnique walks the vector twice: once to count, once to find the first count of $1$. Two passes of $n$ are $2n$ steps, still $O(n)$. No method can stop early, though: whether a value is unique is not known until the last value has been read.

3. The lab#

3.0. Setup and ground rules#

Open the companion code’s cp/cp01 folder in your editor, and a PowerShell terminal in that folder. .\run.ps1 1 builds check.cpp with your drills.h and runs step 1’s checks. Every function starts as a throw that reports “not written yet”; replace it when you write the step. A failing check prints WRONG, what it expected, and, after got, what your code returned.

• Predict before every run, in writing. The orange boxes tell you what to predict.
• Read only the first error. Compiler errors cascade; fix the first one, then rebuild.
• No AI and no searching during an attempt. Use the hint ladders, one rung at a time. Open a step’s complete solution, at the end of the module, only after your own attempt has run against the checks.

3.1. Step 1: count the positives (worked example)#

Type this into drills.h, replacing the throw. Say the promise aloud as you type it.

inline int countPositives(const std::vector<int>& v) {
    int count = 0;                 // promise: count = positive values visited so far
    for (int x : v) {
        if (x > 0) ++count;        // keep the promise for this one value
    }
    return count;                  // every value visited: the promise is the answer
}

3.2. Step 2: finish countEach (partly filled)#

The signature says to build a map; fill the three blanks.

inline std::unordered_map<int, int> countEach(const std::vector<int>& v) {
    ________ counts;            // blank 1: the type the signature returns
    for (int x : v) {
        ________;               // blank 2: one tally for x
    }
    return ________;            // blank 3
}

3.3. Step 3: mostFrequent (partly filled)#

Reuse countEach, then scan the board. The tie rule must be in your code (section 2.3).

inline int mostFrequent(const std::vector<int>& v) {
    std::unordered_map<int, int> counts = countEach(v);
    int best = v[0];               // promise: best = best value scanned so far
    int bestCount = counts[best];  // v[0] is real, so the promise holds now
    for (const auto& [value, count] : counts) {
        // replace best when more often, or equally often with a smaller value
        if (________ || (________ && ________)) {
            best = value;
            bestCount = count;
        }
    }
    return best;
}

3.4. Step 4: firstUnique (on your own)#

Return the index of the first value that appears exactly once, or $-1$. Plan it as two passes (section 2.8): count, then find. Write the promise of each loop as a comment. Hints: hints.

3.5. Step 5: containsDuplicate (on your own)#

Return true as soon as any value is seen a second time. One pass, one map, and you may return early. Hints: hints.

3.6. Step 6: isAnagram (on your own)#

Two strings are anagrams when they use the same characters the same number of times: "listen" and "silent". Count one string, then “spend” the counts with the other. Case and spaces count. Hints: hints.

3.7. Step 7: twoSum, from a blank page (on your own)#

Write it from section 2.4’s idea, without looking at the solutions. Then break it on purpose:

3.8. Step 8: exactSum (on your own)#

3.9. Step 9: countPairsWithSum (on your own)#

Count index pairs $i<j$ that add to the target, in one pass (section 2.4). Hints: hints.

3.10. Step 10: measure it#

4. Practice#

F = foundation; C = standard; T = transfer; S = optional stretch; R = code reading. Work on paper first.

Hint ladders for the lab#

Climb one rung at a time, and try again after each one. Rung 1 is a question, rung 2 points to the idea, and rung 3 is a skeleton with the key parts left for you. Step 1 is worked in full in section 3.1.

5. Code-reading drill: a game server counts its players#

A real-time game server regularly reports its own health: how many players are in each scene (one area of the game world) and how long its recent ticks (passes of its main loop) took. The four excerpts below are adapted from the health-metrics code of a real-time game engine’s server: unrelated lines are left out (marked // ...), and some names are simplified. Read all four, then answer in writing before opening the solutions.

(A) The report’s fields. One ServerMetricsSnapshot, called snap in the other excerpts, holds one report.

struct ServerMetricsSnapshot {
    // ...
    std::unordered_map<std::string, int> sceneCounts;

    // Tick performance (rolling 60s window)
    float avgTickMs = 0.0f;
    float maxTickMs = 0.0f;
    int slowTickCount = 0;
    // ...
    struct TopScene {
        std::string scene;
        int playerCount = 0;
    };
    std::vector<TopScene> topScenes;
    // ...
};

(B) Counting players per scene. forEach calls the function written in place after it (a lambda) once for each player character in the world. cs points to that character’s stats, so its members are reached with ->, and cs->stats.currentScene is the name of the scene the character is in.

if (world_) {
    world_->forEach<CharacterStatsComponent>([&](Entity*, CharacterStatsComponent* cs) {
        if (!cs->stats.currentScene.empty()) {
            snap.sceneCounts[cs->stats.currentScene]++;
        }
    });
}

(C) The last minute of ticks. tickSamples_ holds one sample for each tick of the last 60 seconds; s.totalMs is how long that tick took, in milliseconds.

if (!tickSamples_.empty()) {
    float sum = 0.0f;
    float maxMs = 0.0f;
    int slowCount = 0;
    for (const auto& s : tickSamples_) {
        sum += s.totalMs;
        if (s.totalMs > maxMs) maxMs = s.totalMs;
        if (s.totalMs > 50.0f) slowCount++;
    }
    snap.avgTickMs = sum / static_cast<float>(tickSamples_.size());
    snap.maxTickMs = maxMs;
    snap.slowTickCount = slowCount;
}

(D) The five busiest scenes, and the JSON a dashboard stores. std::sort’s third argument returns true when a belongs before b. nlohmann::json is a widely used JSON library for C++.

// Top scenes (scenes with most players, sorted desc)
for (const auto& [scene, count] : snap.sceneCounts) {
    snap.topScenes.push_back({scene, count});
}
std::sort(snap.topScenes.begin(), snap.topScenes.end(),
          [](const auto& a, const auto& b) { return a.playerCount > b.playerCount; });
if (snap.topScenes.size() > 5) snap.topScenes.resize(5);

// ... later, when the report is saved for the dashboard:
nlohmann::json sceneJson = nlohmann::json::object();
for (const auto& [scene, count] : snap.sceneCounts)
    sceneJson[scene] = count;

6. Mastery gate#

7. Development log#

Add an entry to your development log: what you built (nine functions, about how many lines); your benchmark table and the ratio you predicted next to the ratio you measured; your costliest bug, its symptom, and the check that caught it; and one picture, for example Picture CP01.1 redrawn by hand with your own example.

8. Stretch (optional)#

Frontier connections: where this module’s ideas show up at scale#

• Tokenizers. Byte-pair encoding, used to split text into tokens for language models, repeatedly counts adjacent symbol pairs with a frequency map and merges the most frequent: mostFrequent over pairs (Sennrich, Haddow, and Birch, “Neural machine translation of rare words with subword units”, 2016, arxiv.org/abs/1508.07909). AI Lab Module 2 builds one (section 2E).
• Game servers. A real-time game server counts players per scene, messages per tick, and pending actions per player with exactly this ++counts[key] pattern; the code-reading drill above reads one of those counters.
• Counting at internet scale. When the stream is too large to keep every key, a count–min sketch keeps a few small arrays of counters and answers “about how many?” with a guaranteed error bound (Cormode and Muthukrishnan, Journal of Algorithms 55(1), 2005).

Complete solutions: CP01#

Open a solution only after you have written your own attempt. Compare at the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

Lab step solutions#

Step 1 is worked in full in section 3.1.

L2. countEach.

inline std::unordered_map<int, int> countEach(const std::vector<int>& v) {
    std::unordered_map<int, int> counts;    // the signature says: build a map
    for (int x : v) {
        counts[x]++;                        // a new key starts at 0, then becomes 1
    }
    return counts;                          // promise: the tally of every value
}

Writing counts[x] = 1; would make every count $1$: the step 2 checks for {3, 1, 3, 3}, {-2, -2}, and the large input fail.

L3. mostFrequent.

inline int mostFrequent(const std::vector<int>& v) {
    std::unordered_map<int, int> counts = countEach(v);
    int best = v[0];
    int bestCount = counts[best];
    for (const auto& [value, count] : counts) {
        if (count > bestCount || (count == bestCount && value < best)) {
            best = value;
            bestCount = count;
        }
    }
    return best;
}

For {9, 8, 8, 9, 7, 7} all three values appear twice and the answer is $7$. With only count > bestCount, a tie never replaces best. So {9, 8, 8, 9, 7, 7} returns $9$, the starting value v[0], which breaks the tie rule. And {1, 2, 2, 3, 3} returns whichever of $2$ and $3$ the loop meets first; the standard leaves that order unspecified, so the code alone cannot tell you which.

L4. firstUnique.

inline int firstUnique(const std::vector<int>& v) {
    std::unordered_map<int, int> counts = countEach(v);    // pass 1: count
    for (int i = 0; i < static_cast<int>(v.size()); ++i) {  // pass 2: in order
        if (counts[v[i]] == 1) return i;                    // first count of 1
    }
    return -1;
}

The predictions: firstUnique({7, 7, 8, 9, 8}) is the index $3$, and a version that returns v[i] prints got 9. In {1, 9} both values are unique and the first position, $0$, wins. A second pass that walks the map instead of v can return $1$ there, because the map’s order is not v’s order.

L5. containsDuplicate.

inline bool containsDuplicate(const std::vector<int>& v) {
    std::unordered_map<int, int> seen;   // promise: holds every value visited so far
    for (int x : v) {
        if (seen.count(x)) return true;  // x was visited before: a duplicate
        seen[x] = 1;
    }
    return false;
}

(std::unordered_set<int> from <unordered_set> says the same thing more directly; a map works with the headers you have.) The predictions: {0, 0} gives true and {1} gives false. Recording x before checking makes {1} come out true: the loop finds the very x it just recorded.

L6. isAnagram.

inline bool isAnagram(const std::string& a, const std::string& b) {
    if (a.size() != b.size()) return false;
    std::unordered_map<char, int> counts;
    for (char c : a) counts[c]++;
    for (char c : b) {
        if (--counts[c] < 0) return false;   // b uses c more often than a does
    }
    return true;
}

Why this is enough: the lengths are equal, and no count went below zero, so every count ends at exactly zero. Without the length line, ("aa", "a") and ("listen", "silen") fail: b is shorter, so no count ever goes below zero, and the loop never notices the leftover letters of a. ("a", "aa") still comes out right, because the second 'a' of b drives its count to $-1$.

L7. twoSum.

inline std::vector<int> twoSum(const std::vector<int>& v, int target) {
    std::unordered_map<int, int> indexOf;   // promise: value -> a position visited so far
    for (int j = 0; j < static_cast<int>(v.size()); ++j) {
        int need = target - v[j];
        auto it = indexOf.find(need);
        if (it != indexOf.end()) return {it->second, j};   // look up BEFORE storing v[j]
        indexOf[v[j]] = j;
    }
    return {};
}

Storing first returns {0, 0} for {3, 2, 4}, which fails the validity check (it needs $i<j$). Three step 7 checks fail that way: {3, 2, 4}, {3, 3}, and {5}, where a lone $5$ pairs with itself. The contract keeps every value and the target between $-10^9$ and $10^9$, so target - v[j] stays within $\pm2\times10^9$, inside an int. Without that promise the subtraction itself could overflow, and you would compute it in long long.

L8. exactSum.

inline long long exactSum(const std::vector<int>& v) {
    long long total = 0;          // holds about +-9.2e18
    for (int x : v) total += x;   // x is widened to long long before the addition
    return total;
}

With int total, $2\times10^9+2\times10^9$ overflows; CP01.07 explains the number the check printed after got.

L9. countPairsWithSum.

inline long long countPairsWithSum(const std::vector<int>& v, int target) {
    std::unordered_map<int, long long> seen;  // value -> times seen so far
    long long pairs = 0;                      // promise: pairs among values visited
    for (int x : v) {
        auto it = seen.find(target - x);
        if (it != seen.end()) pairs += it->second;  // one pair per earlier partner
        seen[x]++;                                  // only now count x itself
    }
    return pairs;
}

For $n$ ones and target $2$, every pair counts: $n(n-1)/2=300{,}000\cdot299{,}999/2=44{,}999{,}850{,}000$, about $21$ times what an int holds. Two nested loops would make all $44{,}999{,}850{,}000$ checks; even at the roughly $8\times10^9$ checks per second of section 2.5’s compiler-vectorized brute force, that is five seconds or more.

L10. The benchmark. The brute force should grow about $16$ times for every $4$ times more data ($4^2$); your code about $4$ times, with some noise at small sizes, where fixed costs dominate.

Practice solutions#

Code-reading solutions#

Mastery gate solutions#

inline int countDistinct(const std::vector<int>& v) {
    std::unordered_map<int, int> counts;
    for (int x : v) counts[x]++;
    return static_cast<int>(counts.size());     // one key per different value
}

inline char mostCommonLetter(const std::string& s) {
    int counts[26] = {};
    for (char c : s) counts[c - 'a']++;
    int best = 0;                                // promise: best letter among those scanned
    for (int i = 1; i < 26; ++i) {
        if (counts[i] > counts[best]) best = i;  // strictly greater keeps the earlier letter
    }
    return static_cast<char>('a' + best);
}

inline bool hasPairWithSum(const std::vector<int>& v, int target) {
    std::unordered_map<int, int> seen;
    for (int x : v) {
        if (seen.count(target - x)) return true;  // check before storing
        seen[x] = 1;
    }
    return false;
}

Faded example answer#

int count = 0; (true before any visit), if (x < 0) ++count;, return count;.

Warm-up answers#

1. The key type is std::string (a player’s ID, for example), the value type is PlayerProfile (that player’s record), and a key goes inside the brackets.
2. Start from v[0]: the promise “the largest value visited” must be true before the first pass, and $0$ is not a value in {-3, -1, -2}.
3. Only the second: .size() is a member of std::vector<int>, and an int has no members.