LC Patterns — Graphs

// Adjacency list — the default representation
vector<vector<int>> adj(n);                       // or vector<vector<pair<int,int>>> weighted
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); } // undirected: both

// Grid neighbors
const int DR[] = {-1, 1, 0, 0}, DC[] = {0, 0, -1, 1};

1. Mark visited when you ENQUEUE, not when you dequeue. Marking at dequeue lets a node be enqueued many times before its first visit — on dense grids this silently turns O(V+E) BFS into a TLE. The single most common graph bug.
2. BFS gives shortest paths only on unweighted graphs. The moment edges have weights, BFS's "first arrival = shortest" guarantee dies → Dijkstra. (Weights of only 0 and 1 → 0-1 BFS with a deque; name it, rarely needed.)
3. Recursion depth: a 300×300 grid can produce a 90K-deep DFS → stack overflow in C++. For big grids, prefer BFS or an explicit stack; say why.
4. Directed cycle detection needs three colors (white/gray/black — hitting a gray node = cycle). Undirected needs only visited + skip-parent (a visited non-parent neighbor = cycle). Using the undirected trick on a digraph reports false cycles on diamonds.
5. Dijkstra in C++ = lazy deletion: priority_queue has no decrease-key — push duplicates, and on pop if (d > dist[u]) continue;. Forgetting the stale-skip line is the Dijkstra bug.
6. DSU without both optimizations (path compression + union by size/rank) degrades to O(n) per op — write both by reflex; complexity answer: "amortized α(n), effectively constant."
7. Level-aware BFS uses the queue-size snapshot (same as trees §0.5) or stores the distance with the node — pick one, don't mix.

What it is: Treat a grid as a graph (cells = nodes, 4-neighbors = edges) and find/measure/paint connected regions: count islands, max island area, flood fill. One DFS/BFS from every unvisited land cell; each launch = one component.

Intuition: The outer double-loop plus "launch a traversal on unvisited land, mark everything reachable" is the component-counting algorithm — the traversal claims an entire island, so the number of launches equals the number of islands. Marking visited by mutating the grid ('1' → '0', "sinking" the island) saves the visited array and is idiomatic here — but say you're mutating the input and confirm it's allowed.

Approach:

int numIslands(vector<vector<char>>& g) {
    int m = g.size(), n = g[0].size(), count = 0;
    auto dfs = [&](auto&& self, int r, int c) -> void {
        if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] != '1') return;
        g[r][c] = '0';                            // sink it = mark visited
        for (int k = 0; k < 4; ++k) self(self, r + DR[k], c + DC[k]);
    };
    for (int r = 0; r < m; ++r)
        for (int c = 0; c < n; ++c)
            if (g[r][c] == '1') { ++count; dfs(dfs, r, c); }
    return count;
}

1 1 0
0 1 0
0 0 1

What it is: "How long until all oranges rot?", "each cell's distance to the nearest 0" — distances measured from many sources at once. Seed the BFS queue with all sources at distance 0, then run one ordinary BFS; each cell's first visit is its distance to the nearest source.

Intuition: Imagine a virtual super-source wired to every real source with 0-cost edges — multi-source BFS is just single-source BFS from that phantom node. The wavefront expands from all sources at once, so frontiers meet in the middle; nothing else changes. The inverted framing is the skill: 542 asks "distance from each 1 to the nearest 0" — BFS from all the 0s outward, not from each 1 (which would be O((mn)²)).

Approach:

// 994: minutes until all oranges rot
queue<pair<int,int>> q;                    // seed with ALL rotten oranges
int fresh = 0, minutes = 0;
/* scan grid: push rotten, count fresh */
while (!q.empty() && fresh > 0) {
    int sz = q.size(); ++minutes;                     // one level = one minute
    for (int i = 0; i < sz; ++i) {
        auto [r, c] = q.front(); q.pop();
        for (int k = 0; k < 4; ++k) {
            int nr = r + DR[k], nc = c + DC[k];
            if (/*in bounds*/ && g[nr][nc] == 1) {
                g[nr][nc] = 2; --fresh; q.push({nr, nc});   // mark on enqueue (§0.1)
            }
        }
    }
}
return fresh ? -1 : minutes;

2 1 1
1 1 0
0 1 1

What it is: Shortest transformation sequences where nodes are states and edges are legal moves: word → word by one letter (127), lock code → code by one wheel turn (752), puzzle board → board by one slide (773). No graph is given — you generate neighbors on the fly.

Intuition: "Minimum number of steps" over discrete states = unweighted shortest path = BFS, full stop. The design work is the neighbor function and the state encoding (a string, a tuple, a canonical serialization of a board). Complexity = O(states × neighbor-cost) — estimate the state count out loud (10⁴ lock codes, 9!/2 puzzle boards) to justify feasibility; that estimate is the interview. Bidirectional BFS (expand from both ends, always grow the smaller frontier) halves the exponent — name it for 127, implement only if pushed.

Approach (skeleton):

unordered_set<string> visited{start};
queue<string> q; q.push(start);
int steps = 0;
while (!q.empty()) {
    int sz = q.size();
    for (int i = 0; i < sz; ++i) {
        string cur = q.front(); q.pop();
        if (cur == target) return steps;
        for (string& nxt : neighbors(cur))          // generate moves; skip banned states
            if (visited.insert(nxt).second)          // insert-if-absent = mark on enqueue
                q.push(nxt);
    }
    ++steps;
}
return -1;

What it is: Shortest path where the answer depends on more than location: "you may eliminate up to k obstacles" (1293), "visit all nodes" (847). The node becomes a tuple — (cell, eliminations left), (vertex, visited-mask) — and BFS proceeds normally over the bigger state space.

Intuition: When two arrivals at the same cell aren't interchangeable (one has budget left, one doesn't), the cell alone is an underspecified state — BFS's "first visit is best" guarantee only holds for the full tuple. This is the DP dimension-selection question applied to search: add exactly the dimensions that make states self-contained, no more. Prune dominated states where cheap (in 1293, arriving with more budget strictly dominates — track best-budget-per-cell instead of a full visited-set).

Approach (1293 core):

// state: (r, c, k_remaining); visited: best k seen per cell
vector<vector<int>> bestK(m, vector<int>(n, -1));
queue<array<int,3>> q; q.push({0, 0, k}); bestK[0][0] = k;
// standard level BFS; neighbor transition:
int nk = kCur - grid[nr][nc];                    // pay 1 to cross an obstacle
if (nk > bestK[nr][nc]) { bestK[nr][nc] = nk; q.push({nr, nc, nk}); }

0 0 0
1 1 0
0 0 0
0 1 1
0 0 0

What it is: The given-adjacency version of Pattern 1: count provinces from an adjacency matrix, decide if you can visit every room following keys, check if there's a path from A to B. Build/interpret the adjacency structure, run DFS/BFS, count launches or check reachability.

Intuition: Nothing new algorithmically — the pattern exists because representation handling is the tested skill: adjacency matrix (547) vs adjacency list (841) vs raw edge list (1971 — build the list first, or skip traversal entirely with DSU). Choosing DFS vs BFS vs DSU here is pure taste; saying "any of the three works — I'll use X because ⟨fewest lines / no recursion risk / queries suggest DSU⟩" is exactly the judgment sentence interviewers want.

Approach:

int findCircleNum(vector<vector<int>>& isConnected) {   // 547: adjacency MATRIX
    int n = isConnected.size(), comps = 0;
    vector<bool> vis(n, false);
    auto dfs = [&](auto&& self, int u) -> void {
        vis[u] = true;
        for (int v = 0; v < n; ++v)
            if (isConnected[u][v] && !vis[v]) self(self, v);
    };
    for (int u = 0; u < n; ++u)
        if (!vis[u]) { ++comps; dfs(dfs, u); }
    return comps;
}

What it is: Order items under prerequisite constraints, or decide it's impossible (a cycle): course schedule, build order, safe states. Kahn's algorithm: repeatedly take a node with indegree 0, emit it, decrement its neighbors' indegrees. Fewer emitted than n ⇒ cycle.

Intuition: A node with indegree 0 has no unmet prerequisites — safe to do now; doing it can only unlock others. If the queue empties early, every remaining node waits on another remaining node — that circular waiting is the cycle, and Kahn's detects it for free (no separate cycle pass). The DFS alternative (three colors, §0.4; reverse-post-order = topo order) is equivalent — know both, lead with Kahn's. 802 is the same idea on reversed edges: safe nodes = nodes that can't reach a cycle = run Kahn's on the reverse graph from the terminals.

Approach:

vector<int> findOrder(int n, vector<vector<int>>& pre) {  // 210
    vector<vector<int>> adj(n); vector<int> indeg(n, 0);
    for (auto& p : pre) { adj[p[1]].push_back(p[0]); ++indeg[p[0]]; }  // prereq → course
    queue<int> q;
    for (int u = 0; u < n; ++u) if (!indeg[u]) q.push(u);
    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);
    }
    return (int)order.size() == n ? order : vector<int>{};  // short ⇒ cycle ⇒ impossible
}

What it is: A forest of parent pointers answering "are x and y in the same group?" and "merge these groups" in near-O(1): the redundant connection (the edge that closes a cycle), account merges (emails as nodes), removing max stones (row/col as meta-nodes). The tool of choice when edges arrive incrementally or the problem is phrased as merging.

Intuition: Each group is a tree; find walks to the root (with path compression: point everyone at the root as you return); union hangs the smaller tree under the larger (by size/rank). Together: amortized α(n) ≈ constant. DSU vs DFS: DFS answers connectivity for a fixed graph; DSU stays correct as edges stream in — 684 is literally "the first edge whose endpoints already connect." The modeling trick that unlocks hard DSU problems: nodes needn't be the obvious entities — union stones with row-id and col-id meta-nodes (947), union emails (721), and components fall out.

Approach:

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }   // path compression
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;                  // already connected — 684's answer moment
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a; sz[a] += sz[b];
        return true;
    }
};

What it is: Can the nodes be split into two groups so every edge crosses between groups? (Equivalently: is there no odd cycle?) BFS/DFS-color each node opposite to its parent; an edge joining two same-colored nodes = not bipartite.

Intuition: If a two-group split exists, the coloring is forced once a component's first node is colored — so greedy propagation either completes (bipartite) or hits a contradiction (an odd cycle, the only obstruction). The recognition skill: problems that never say "bipartite" — "split people into two teams given rivalries" (886) is this; conflict-edges + two groups = 2-coloring.

Approach:

bool isBipartite(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> color(n, -1);
    for (int s = 0; s < n; ++s) {                  // graph may be disconnected!
        if (color[s] != -1) continue;
        queue<int> q; q.push(s); color[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) { color[v] = color[u] ^ 1; q.push(v); }
                else if (color[v] == color[u]) return false;
            }
        }
    }
    return true;
}

What it is: Cheapest path when edges have costs: network delay (743), cheapest flight with ≤ k stops (787), minimize the maximum step (1631). Dijkstra = BFS upgraded with a priority queue (settle nodes cheapest-first); Bellman-Ford = relax all edges in rounds (round i = best using ≤ i edges).

Intuition: Dijkstra's invariant: with non-negative weights, the unsettled node with the smallest tentative distance can't be improved (any detour costs ≥ 0 more) — so settle it. That argument dies with negative edges or hop limits: 787's "≤ k stops" makes Dijkstra's greedy commitment wrong (a pricier-but-shorter prefix may win later) — Bellman-Ford's round structure is the hop count, run k+1 rounds against a frozen-snapshot copy. 1631 shows the objective swap: minimize the max edge instead of the sum — Dijkstra works with alt = max(dist[u], w).

Approach (Dijkstra with lazy deletion — §0.5):

vector<int> dist(n + 1, INT_MAX); dist[src] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;  // (dist, node)
pq.push({0, src});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;                     // stale entry — the mandatory line
    for (auto [v, w] : adj[u])
        if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); }
}

What it is: Connect all nodes at minimum total edge cost (1584: cities as points, cost = manhattan distance). Kruskal's: sort edges, greedily take any edge joining two different components (DSU — Pattern 7 as a subroutine). Prim's: grow one tree, always adding the cheapest edge leaving it (Dijkstra's skeleton with key = w instead of dist + w).

Intuition: Both are the cut property: the cheapest edge crossing any cut is safe to take (exchange argument: any spanning tree avoiding it can swap it in with no cost increase — deliver this in two sentences when asked "why is greedy correct?"). Kruskal = the cut property applied globally (sort once); Prim = applied to the growing-tree cut. Choose by shape: sparse/edge-list given → Kruskal; dense/complete graphs (1584's n² point pairs) → Prim with the O(n²) array version, no heap needed.

Approach (Kruskal core):

sort(edges.begin(), edges.end());                  // (w, u, v)
DSU dsu(n);
int total = 0, used = 0;
for (auto& [w, u, v] : edges)
    if (dsu.unite(u, v)) { total += w; if (++used == n - 1) break; }
return total;

What it is: Problems where the work is modeling: clone a graph (133 — traverse while duplicating, a hashmap old→new as the visited set), evaluate division (399 — a/b = 2.0 is a weighted edge; a query a/c is a path whose answer is the product of edge weights along it).

Intuition: 133's insight: the old→new map is the visited marker — create-on-first-encounter, reuse ever after; wiring neighbors happens naturally in traversal order. 399's insight is the transferable one: relations compose along paths — division ratios multiply, currency conversions multiply, "same as" relations just connect. Whenever pairwise relations must be chained, build the graph and let traversal (or weighted DSU) do the algebra. Costume-spotting is the entire skill this pattern trains.

Approach (133 core):

unordered_map<Node*, Node*> mp;                    // old → new; doubles as visited
Node* clone(Node* u) {
    if (!u) return nullptr;
    if (auto it = mp.find(u); it != mp.end()) return it->second;
    Node* nu = new Node(u->val);
    mp[u] = nu;                                    // register BEFORE recursing — cycles!
    for (Node* v : u->neighbors) nu->neighbors.push_back(clone(v));
    return nu;
}