The TEACH cheat sheet

// LC 994 · BFS, multi-source shortest steps on a grid
// O(V + E) time, O(V) space (here V = m * n)
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int orangesRotting(vector<vector<int>> g) {            // by value: we mark cells in place
    int m = g.size(), n = g[0].size(), fresh = 0, t = 0;
    queue<pair<int, int>> q;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (g[i][j] == 2) q.push({i, j});
            else if (g[i][j] == 1) fresh++;
        }
    int d[] = {0, 1, 0, -1, 0};
    for (; !q.empty() && fresh; t++)                    // one level per minute
        for (int s = q.size(); s--; ) {
            auto [x, y] = q.front(); q.pop();
            for (int k = 0; k < 4; k++) {
                int a = x + d[k], b = y + d[k + 1];
                if (a < 0 || b < 0 || a >= m || b >= n || g[a][b] != 1) continue;
                g[a][b] = 2; fresh--;                   // mark seen when pushing
                q.push({a, b});
            }
        }
    return fresh ? -1 : t;
}

# LC 994 · BFS, multi-source shortest steps on a grid
# O(V + E) time, O(V) space (here V = m * n)
from collections import deque

def oranges_rotting(grid):
    g = [row[:] for row in grid]                        # copy: we mark cells in place
    m, n = len(g), len(g[0])
    q = deque((i, j) for i in range(m) for j in range(n) if g[i][j] == 2)
    fresh = sum(row.count(1) for row in g)
    t = 0
    while q and fresh:
        for _ in range(len(q)):                         # one level per minute
            x, y = q.popleft()
            for a, b in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                if 0 <= a < m and 0 <= b < n and g[a][b] == 1:
                    g[a][b] = 2                         # mark seen when pushing
                    fresh -= 1
                    q.append((a, b))
        t += 1
    return -1 if fresh else t

// Hash map and set: unordered_map, unordered_set
#include <optional>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

unordered_map<int, int> countFreq(const vector<int>& a) {
    unordered_map<int, int> cnt;
    for (int x : a) cnt[x]++;                       // get + put: O(1) avg per key
    return cnt;                                     // worst case, all keys collide: O(n) per op
}
bool hasKey(const unordered_map<int, int>& m, int k) { return m.count(k) > 0; }   // contains: O(1) avg
void removeKey(unordered_map<int, int>& m, int k) { m.erase(k); }                 // delete: O(1) avg
int sumValues(const unordered_map<int, int>& m) {   // iterate: O(n)
    int s = 0;
    for (auto& [k, v] : m) s += v;
    return s;
}
optional<int> firstRepeat(const vector<int>& a) {   // "have I seen this?", nullopt if none
    unordered_set<int> seen;
    for (int x : a)
        if (!seen.insert(x).second) return x;       // insert fails if present: O(1) avg
    return nullopt;
}

# Hash map and set: dict, Counter, set
from collections import Counter, defaultdict

def count_freq(a):
    return Counter(a)                       # counts in one pass: O(n), each put O(1) avg

def group_by_parity(a):
    groups = defaultdict(list)              # missing key starts as []
    for x in a:
        groups[x % 2].append(x)             # get + put: O(1) avg
    return groups

def has_key(m, k): return k in m            # contains: O(1) avg
def remove_key(m, k): m.pop(k, None)        # delete: O(1) avg
def sum_values(m): return sum(m.values())   # iterate: O(n)
# worst case, all keys collide: O(n) per operation

def first_repeat(a):                        # "have I seen this?", None if none
    seen = set()
    for x in a:
        if x in seen: return x              # contains: O(1) avg
        seen.add(x)                         # put: O(1) avg
    return None