Patterns & Templates — Copy-Paste C++ You Should Memorize¶
“The study partner does not want to see you invent DFS. They want to see you deploy DFS and spend your creative budget on the twist.”
Every template below is: (1) short, (2) compiles clean under -std=c++20 -Wall -Wextra -Wpedantic, (3) something you should be able to type from memory in under two minutes by the end of W15. Do not paraphrase; internalize the exact form.
1. DFS — recursive¶
std::vector<std::vector<int>> g; // adjacency list, size n
std::vector<int> visited; // size n, initially 0
void dfs(int u) {
visited[u] = 1;
for (int v : g[u]) {
if (!visited[v]) dfs(v);
}
}
Notes. For graphs with n > ~10^5, recursive DFS may blow the stack (default ~1 MB on Linux, ~512 KB on Mac). Switch to iterative when depth risk is real.
2. DFS — iterative (explicit stack)¶
void dfs_iter(int start) {
std::stack<int> st;
st.push(start);
while (!st.empty()) {
int u = st.top(); st.pop();
if (visited[u]) continue;
visited[u] = 1;
for (int v : g[u]) {
if (!visited[v]) st.push(v);
}
}
}
Note. Marking visited on pop, not on push, is safer against pushing the same node multiple times.
3. BFS — with parent tracking (for path reconstruction)¶
std::vector<int> parent(n, -1);
std::vector<int> dist(n, -1);
std::queue<int> q;
q.push(start);
dist[start] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
parent[v] = u;
q.push(v);
}
}
}
// Reconstruct path from `target` back to `start`:
std::vector<int> path;
for (int cur = target; cur != -1; cur = parent[cur]) path.push_back(cur);
std::reverse(path.begin(), path.end());
4. BFS on a grid (4-neighborhood)¶
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
int bfs_grid(const std::vector<std::vector<int>>& grid,
std::pair<int,int> src, std::pair<int,int> dst) {
int R = grid.size(), C = grid[0].size();
std::vector<std::vector<int>> dist(R, std::vector<int>(C, -1));
std::queue<std::pair<int,int>> q;
q.push(src);
dist[src.first][src.second] = 0;
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
if (std::make_pair(r, c) == dst) return dist[r][c];
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
if (grid[nr][nc] == 0) continue; // obstacle
if (dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
return -1;
}
5. Dijkstra — priority_queue<pair<int,int>>¶
using P = std::pair<long long, int>; // {dist, node}
std::vector<std::vector<std::pair<int,int>>> adj; // adj[u] = {v, weight}
std::vector<long long> dijkstra(int src, int n) {
std::vector<long long> dist(n, LLONG_MAX);
std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // stale entry, skip
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
Notes. The “stale entry” check (if (d > dist[u]) continue;) is why lazy deletion works instead of a decrease-key heap. Complexity: O((V + E) log V).
Trap. Dijkstra requires non-negative weights. For any negative edge, switch to Bellman-Ford (O(VE)).
6. 0-1 BFS (deque)¶
When edge weights are only 0 or 1, you can beat Dijkstra with a deque — O(V + E) instead of O((V + E) log V).
std::vector<int> zero_one_bfs(int src, int n,
const std::vector<std::vector<std::pair<int,int>>>& adj) {
std::vector<int> dist(n, INT_MAX);
std::deque<int> dq;
dist[src] = 0;
dq.push_front(src);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v);
else dq.push_back(v);
}
}
}
return dist;
}
When it helps. Grids where some moves are free and others cost 1 (LC 1368, 2290).
7. Topological sort — Kahn’s (BFS-based)¶
std::vector<int> topo_kahn(int n, const std::vector<std::vector<int>>& adj) {
std::vector<int> indeg(n, 0);
for (int u = 0; u < n; ++u)
for (int v : adj[u]) ++indeg[v];
std::queue<int> q;
for (int i = 0; i < n; ++i)
if (indeg[i] == 0) q.push(i);
std::vector<int> order;
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : adj[u]) {
if (--indeg[v] == 0) q.push(v);
}
}
if ((int)order.size() != n) return {}; // cycle
return order;
}
8. Topological sort — DFS-based (post-order reverse)¶
std::vector<int> topo_dfs(int n, const std::vector<std::vector<int>>& adj) {
std::vector<int> color(n, 0); // 0=white, 1=gray, 2=black
std::vector<int> order;
bool has_cycle = false;
std::function<void(int)> dfs = [&](int u) {
if (has_cycle) return;
color[u] = 1;
for (int v : adj[u]) {
if (color[v] == 1) { has_cycle = true; return; }
if (color[v] == 0) dfs(v);
}
color[u] = 2;
order.push_back(u);
};
for (int i = 0; i < n; ++i)
if (color[i] == 0) dfs(i);
if (has_cycle) return {};
std::reverse(order.begin(), order.end());
return order;
}
9. Backtracking skeleton (subsets / permutations / combinations)¶
std::vector<std::vector<int>> subsets(const std::vector<int>& nums) {
std::vector<std::vector<int>> out;
std::vector<int> path;
std::function<void(int)> bt = [&](int start) {
out.push_back(path);
for (int i = start; i < (int)nums.size(); ++i) {
path.push_back(nums[i]);
bt(i + 1);
path.pop_back();
}
};
bt(0);
return out;
}
Notes. path is captured by reference in the lambda so the push/pop mutates the shared vector. Use i + 1 (not start + 1) for subsets/combinations; use a used[] array for permutations.
10. Sliding window (variable size, longest valid substring)¶
int longest_valid(const std::string& s) {
int l = 0, best = 0;
std::array<int, 128> cnt{};
for (int r = 0; r < (int)s.size(); ++r) {
cnt[(unsigned char)s[r]]++;
while (/* invariant broken */) {
cnt[(unsigned char)s[l]]--;
++l;
}
best = std::max(best, r - l + 1);
}
return best;
}
11. Binary search on answer¶
auto binary_search_answer = [&](auto&& feasible) -> long long {
long long lo = LO, hi = HI; // define bounds for your problem
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
};
Example use — Koko eating bananas (LC 875):
auto canFinish = [&](long long k) {
long long h = 0;
for (int p : piles) h += (p + k - 1) / k; // ceil division
return h <= H;
};
int answer = (int)binary_search_answer(canFinish);
Trap. mid = lo + (hi - lo) / 2 — not (lo + hi) / 2 — to avoid overflow when lo + hi exceeds int max.
12. DP: memo → tab conversion¶
Memoized (top-down):
std::vector<std::vector<int>> memo;
int solve(int i, int j) {
if (/* base case */) return /* base value */;
int& r = memo[i][j];
if (r != -1) return r;
return r = /* recurrence in terms of solve(i-1, j) etc. */;
}
// Setup:
memo.assign(n, std::vector<int>(m, -1));
int answer = solve(n - 1, m - 1);
Tabulated (bottom-up) — same recurrence, iterative:
std::vector<std::vector<int>> dp(n, std::vector<int>(m, 0));
// Fill base cases (row 0 / col 0 typically):
// dp[0][j] = ...; dp[i][0] = ...;
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
dp[i][j] = /* recurrence in terms of dp[i-1][j], dp[i][j-1], ... */;
}
}
int answer = dp[n-1][m-1];
Then space-optimize if needed: if dp[i][*] only reads dp[i-1][*], keep two rows. If only dp[i-1][j-1], keep one row and traverse right-to-left. Only do this after verifying correctness of the full 2D table.
13. Custom hash to prevent unordered_map TLE¶
Drop this alongside your Dijkstra / graph templates — use it whenever your unordered_map mysteriously TLEs on the last two test cases.
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x100000;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t seed =
std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + seed);
}
};
// Usage:
std::unordered_map<int, int, custom_hash> safe_map;
14. Grid neighbor helper (4-way and 8-way)¶
constexpr int dr4[4] = {-1, 1, 0, 0};
constexpr int dc4[4] = {0, 0, -1, 1};
constexpr int dr8[8] = {-1,-1,-1, 0, 0, 1, 1, 1};
constexpr int dc8[8] = {-1, 0, 1,-1, 1,-1, 0, 1};
template <typename F>
void for_each_neighbor4(int r, int c, int R, int C, F&& f) {
for (int k = 0; k < 4; ++k) {
int nr = r + dr4[k], nc = c + dc4[k];
if (0 <= nr && nr < R && 0 <= nc && nc < C) f(nr, nc);
}
}
15. Fast I/O + boilerplate main()¶
#include <bits/stdc++.h> // fine for studies; NOT for production
using namespace std; // fine for studies; NOT for production
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// ...
return 0;
}
Note. #include <bits/stdc++.h> is a GCC-specific catch-all. On Apple’s Clang it does not exist; use explicit includes if you are compiling locally on macOS. On LeetCode it is fine.
What most people get wrong¶
They copy these templates once, understand them, and never type them by hand again. Then in an study they cannot reproduce the Dijkstra stale-entry check or the topo-sort cycle detection. The templates in this file are not references; they are exercises. Type all fifteen out this weekend. Type them again next weekend. Every subsequent NeetCode problem you solve, use your typed template, not a fresh look-up. That is how they enter fingers.
One more: they treat these templates as immutable. In reality, every problem is a variant. The template gets you 80% there; the variant is what you actually solve. Do not fight the variant — embrace it.