Part 4 of 6. Graphs — the most expansive topic in interviews. BFS/DFS on grids and adjacency lists, topological sort, Dijkstra, Bellman-Ford, Union-Find, and the hardest graph problems that separate Codeforces Pupil from Expert.
BFS (Queue, level-by-level): Use when you need the SHORTEST PATH in an unweighted graph, minimum number of steps/moves, or level-order processing. BFS guarantees the first time you reach a node is via the shortest path.
DFS (Stack/Recursion, depth-first): Use when you need to explore all paths, detect cycles, find connected components, or check reachability. DFS explores one branch fully before backtracking.
Grid = Graph: Every grid problem where you move between cells is a graph. Cells are nodes, valid moves are edges. The 4-directional movement array dx[]={0,0,1,-1}, dy[]={1,-1,0,0} is your adjacency list.
Count the number of islands in a 2D binary grid ('1'=land, '0'=water). An island is a group of '1's connected 4-directionally.
[["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]3Scan the grid. When you find an unvisited '1': increment count, then DFS from that cell to mark all connected land as visited (change to '0'). Each DFS call explores one complete island. Count = number of DFS calls made.
Return the maximum area (number of cells) of an island. Return 0 if no island.
Same flood fill as Q106, but DFS now returns the count of cells in the island instead of just marking. Each recursive call returns 1 (current cell) + sum of sizes from valid neighbours.
Grid: 0=empty, 1=fresh orange, 2=rotten. Each minute, rotten oranges rot adjacent (4-dir) fresh ones. Return minimum minutes until no fresh oranges, or -1 if impossible.
[[2,1,1],[1,1,0],[0,1,1]]4Key insight: ALL rotten oranges start spreading at minute 0 simultaneously. Push them ALL into the BFS queue before starting. Then process level by level — each level = 1 minute. Count fresh oranges; after BFS, if any remain → return -1.
Given a binary matrix, return a matrix of the same size where each cell contains the distance to the nearest 0.
[[0,0,0],[0,1,0],[1,1,1]][[0,0,0],[0,1,0],[1,2,1]]Don't BFS from each 1 to find its nearest 0 (that would be O(n²)). Instead, start BFS from ALL 0 cells simultaneously. Distance = BFS level when you first reach a cell. This is the same multi-source BFS pattern as Q108.
Fill each empty room (INF) with distance to its nearest gate (0). Walls are -1. Multi-source BFS from all gates simultaneously.
Find all cells from which water can flow to BOTH the Pacific (top/left edges) and Atlantic (bottom/right edges). Water flows to equal or lower neighbours.
Instead of simulating water flow downward from each cell (O(n²m²)), reverse: BFS/DFS uphill from each ocean's border cells. A cell can "reach the ocean" if the next cell is equal or higher. Do this separately for Pacific and Atlantic. Cells in both sets are the answer.
Flip all 'O' regions not connected to the border to 'X'. Border-connected 'O' regions remain.
[["X","X","X","X"],
["X","O","O","X"],
["X","X","O","X"],
["X","O","X","X"]][["X","X","X","X"],
["X","X","X","X"],
["X","X","X","X"],
["X","O","X","X"]]Instead of finding enclosed regions (hard), find border-connected 'O' regions (easy: DFS from each border 'O'). Mark them safe (e.g., 'S'). Then flip all remaining 'O' to 'X' and restore 'S' to 'O'.
Given beginWord, endWord, and a wordList, find the shortest transformation sequence from begin to end where each step changes exactly one letter and each intermediate word must be in wordList. Return the number of words in the shortest sequence (0 if impossible).
begin="hit", end="cog"
list=["hot","dot","dog","lot","log","cog"]5hit→hot→dot→dog→cogThis is BFS on an implicit graph. Each word is a node. Two words are connected if they differ by exactly one character. BFS finds the shortest path from beginWord to endWord. For each word in the queue, try changing each character to 'a'-'z' and check if the result is in the word set.
Deep copy (clone) an undirected graph. Each node has a value and a list of neighbours.
Use a hash map: visited[old_node] = new_node. DFS: if current node is already in map, return its clone (handles cycles). Otherwise: create clone, add to map, recursively clone all neighbours and add them to the clone's neighbour list.
Given n nodes (0 to n-1) and edges list, find the number of connected components.
A graph is bipartite if nodes can be split into two sets where every edge connects a node from set A to set B (no edges within a set). Check if the given graph is bipartite.
BFS/DFS with two colors (0 and 1). Color each node; assign the opposite color to all neighbours. If a neighbour already has the same color as the current node → conflict → not bipartite. Equivalent to: does the graph contain an odd-length cycle?
A chess king moves to any of 8 adjacent cells per step. Given a sequence of points to visit in order, find the minimum total steps.
A king can move diagonally so it covers both horizontal and vertical distance simultaneously. To move from (x1,y1) to (x2,y2): the king needs max(|x2-x1|, |y2-y1|) steps — diagonal moves cover both coordinates at once.
Find the shortest clear path (all 0s) from top-left to bottom-right of a binary matrix. Movement is 8-directional. Return path length or -1.
Kahn's Algorithm (BFS): Compute in-degrees. Push all nodes with in-degree 0 into a queue. Process: pop node, add to order, decrement neighbours' in-degrees. If a neighbour reaches 0, push it. If final order size < n → cycle exists.
DFS-based: Run DFS. After exploring all neighbours of a node, push it onto a stack. Reverse the stack = topological order. Use 3-state coloring (white/grey/black) for cycle detection.
When to use: Task scheduling, build systems, course prerequisites, dependency resolution — anything with "A must come before B" constraints.
n courses, prereqs[i]=[a,b] means take b before a. Can you finish all courses? (= Does the prerequisite graph have a cycle?)
n=2, prereqs=[[1,0]]truen=2, prereqs=[[1,0],[0,1]]false (cycle)Build a directed graph where edge b→a means "b is prerequisite of a". Apply Kahn's algorithm. If all n nodes are processed (added to topological order), no cycle exists and all courses can be finished.
Return the order in which to take courses such that all prerequisites are satisfied. Return empty array if impossible (cycle).
Given a sorted alien language dictionary (sorted by alien alphabet), derive the character ordering. Return one valid ordering of characters, or "" if invalid.
["wrt","wrf","er","ett","rftt"]"wertf"Compare each pair of adjacent words. Find the first position where they differ — that character must come before the other in the alien alphabet. Build a directed graph from these constraints. Apply topological sort. Watch for: word2 is prefix of word1 (invalid), cycles (invalid).
Check if org is the only shortest supersequence that can be reconstructed from sequences. I.e., the topological order is unique and matches org.
Apply Kahn's algorithm. At each step, if the queue has more than 1 element, multiple valid orderings exist → org cannot be the unique reconstruction. Also verify each step matches org.
A node is "safe" if every path from it eventually leads to a terminal node (no cycles reachable). Return all safe nodes sorted.
In the reversed graph, terminal nodes (sinks → no outgoing) become sources. Safe nodes in original = nodes reachable from terminals in reversed graph = apply Kahn's starting from nodes with outdegree 0 in original (= indegree 0 in reversed).
Find all roots of minimum height trees in an undirected tree with n nodes. Return all such root labels.
The center of a tree minimizes its height (at most 2 central nodes). Use a topological-sort-like approach: repeatedly remove leaf nodes (degree 1) layer by layer. The last 1 or 2 remaining nodes are the centers and the answer.
n courses with durations and prerequisites. Courses can be taken in parallel. Find the minimum time to finish all courses (= longest path in DAG = critical path).
Process nodes in topological order. dp[v] = earliest finish time for course v = time[v] + max(dp[u]) for all prerequisites u. The answer is max(dp[i]) over all nodes.
Unweighted graph: BFS. O(V+E). First time a node is visited = shortest path.
Weighted graph, no negative edges: Dijkstra. O((V+E) log V). Use a min-heap.
Weighted graph, negative edges (no neg cycle): Bellman-Ford. O(VE). Relax all edges V-1 times.
Negative cycle detection: Bellman-Ford Vth iteration. If relaxation still happens → negative cycle.
All-pairs shortest path: Floyd-Warshall. O(V³). DP through intermediate nodes.
DAG shortest/longest path: Topological order DP. O(V+E).
Network of n nodes with directed weighted edges. Signal sent from node k. Return time for all nodes to receive the signal, or -1 if not all reachable. (= single-source shortest path, find max)
Classic Dijkstra from source k. The time for node i to receive signal = shortest path from k to i. The time for ALL nodes to receive signal = maximum shortest path distance from k.
n cities, flights with prices. Find cheapest price from src to dst with at most k stops. Return -1 if impossible. (At most k stops = at most k+1 edges)
n=4,flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
src=0,dst=3,k=1700Standard Bellman-Ford relaxes V-1 times for shortest paths. Here, relax exactly k+1 times — this finds shortest paths using at most k+1 edges (k stops). Use a copy of the distance array per iteration to prevent using more edges than allowed in one iteration.
Find a path from top-left to bottom-right of a grid minimizing the maximum absolute difference in heights between consecutive cells.
Dijkstra works here because the "distance" = max absolute difference along the path, and this is monotone (adding more edges can only increase or maintain the max). Edge weight = abs(height[nr][nc] - height[r][c]). Path "distance" = max edge encountered, not sum.
Find the city with the fewest other cities reachable within a distance threshold. All-pairs shortest paths needed.
Init dist[i][i]=0, dist[i][j]=edge weight or INF. For each intermediate node k: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Then count reachable cities per city and find the answer.
Grid where grid[i][j] = time when cell becomes accessible. Find the minimum time T such that there is a path from top-left to bottom-right where all cells are accessible at time T.
Grid has arrows (1=right,2=left,3=down,4=up). Cost 0 to follow arrow, cost 1 to change it. Find minimum cost path from top-left to bottom-right.
When edge weights are only 0 or 1, use a deque instead of a priority queue. Cost 0 → push to front. Cost 1 → push to back. This gives Dijkstra-like guarantees in O(V+E) instead of O((V+E) log V).
Find the Kth shortest path from source to destination in a weighted directed graph (paths can repeat nodes).
In standard Dijkstra, skip a node once visited. For Kth shortest path: allow each node to be processed up to K times. The Kth time destination is popped = Kth shortest path. Use a visit counter array.
Two operations, both near-O(1) with path compression + union by rank:
find(x): Return the root/representative of x's component. Path compression: make every node on the path point directly to root.
unite(x,y): Merge two components. Union by rank: attach smaller tree under larger to keep height low.
When to use: Detecting cycles in undirected graphs. Counting connected components. Kruskal's MST. Dynamic connectivity problems. "Are x and y in the same group?"
Given a tree with one extra edge creating a cycle. Find and return the redundant edge. (= First edge that connects two nodes already in the same component)
Process edges one by one. For each edge (u,v): if find(u) == find(v) → they're already connected → this edge creates a cycle → it's the redundant edge. Otherwise unite(u, v).
m×n grid, initially water. Process operations adding land cells one at a time. After each addition, return the current number of islands.
Maintain a DSU for land cells. When adding cell (r,c): create a new component (islandCount++). For each of 4 neighbours that are land and in a different component: unite them (islandCount--). DSU handles all merging efficiently.
Find the minimum spanning tree (MST) of a weighted undirected graph. Return the total weight of the MST.
Sort all edges by weight. Process in order: if an edge connects two different components (DSU find gives different roots) → add it to MST (unite). Otherwise skip (would create cycle). Stop when n-1 edges added.
Merge accounts with overlapping emails. Each account is [name, email1, email2...]. If two accounts share an email, they belong to the same person. Return merged accounts sorted.
Map each email to an index. For each account, unite all emails with the first email of that account. After all unions, group emails by their root component. Sort each group and prepend the name.
You can change one 0 to 1. Find the size of the largest island you can create after this change.
Step 1: Use DSU to label all existing islands and record their sizes. Step 2: For each 0 cell, check 4 neighbours' island roots (use a set to avoid double-counting same island). The best flip = 1 + sum of distinct neighbour island sizes.
Find all critical connections (bridges) in a network — edges whose removal would disconnect the graph.
DFS assigns each node a discovery time. low[v] = minimum discovery time reachable from v's subtree (including back edges). Edge (u,v) is a bridge if low[v] > disc[u] — v's subtree cannot reach u or above without this edge.
Find all Strongly Connected Components (SCCs) in a directed graph. An SCC is a maximal group of nodes where every node is reachable from every other.
Pass 1: DFS on original graph, record finish order (push to stack when DFS completes a node). Pass 2: Reverse all edges. Process nodes in reverse finish order (pop from stack). Each DFS call in pass 2 explores one complete SCC.
Find the longest path in a DAG (weighted or unweighted). Used in: critical path analysis, scheduling, project management.
Process nodes in topological order. For each node u: for each edge u→v, update dp[v] = max(dp[v], dp[u] + weight). The final answer is max(dp[i]). To reconstruct the path, track the predecessor that gave the maximum.