Step 4 of 6

unordered_map

std::unordered_map has the same interface as std::map ([], find, contains, insert, erase), but it's built on a hash table instead of a tree. The trade:

When you don't care about order, unordered_map is usually faster. The classic use is remembering what you've seen so you don't have to search again.

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

// Index of the first repeated word, or -1.
int first_repeat(const std::vector<std::string>& words) {
    std::unordered_map<std::string, int> first_seen;   // word -> index where it appeared
    for (int i = 0; i < (int)words.size(); i++) {
        auto it = first_seen.find(words[i]);
        if (it != first_seen.end()) {
            std::cout << "'" << words[i] << "' first seen at " << it->second << "\n";
            return i;
        }
        first_seen[words[i]] = i;
    }
    return -1;
}

int main() {
    std::cout << first_repeat({"red", "green", "blue", "green", "red"}) << "\n";
    std::cout << first_repeat({"a", "b", "c"}) << "\n";
}

'green' first seen at 1
3
-1

Why this is fast

The naive way to find a repeat compares every pair of words: about n * n / 2 comparisons. With a hash map, each word is checked and stored once, so the whole scan is O(n). Trading a little memory for a lot of speed is one of the most important ideas in algorithms, and the "one pass with a hash map" pattern solves a huge number of interview problems.

The order of the check matters

Notice the loop looks up first, then inserts. If it inserted first, every word would immediately "find itself". The same care applies to your exercise: check for the partner before storing the current element, so an element is never paired with itself.

Your task

Write std::pair<int, int> two_sum(const std::vector<int>& v, int target) that returns the indexes {i, j} (with i < j) of two numbers adding up to target, or {-1, -1}. Do it in one pass: for each element, check whether target - v[j] was seen before.

Challenge 2

Write char first_unique(const std::string& s) that returns the first character appearing exactly once in the string, or '\0' if there is none. Count with a std::unordered_map<char, int>, then make a second pass over the string.

Challenge 3

Write int longest_unique_run(const std::string& s): the length of the longest substring with no repeated characters. "abcabcbb" gives 3 ("abc"). Keep a window [start, i], and an unordered_map from each character to the index where it was last seen; when the current character was seen inside the window, move start past it.

Previous: std::set Next: pair and tuple