Graph DFS / Flood Fill
Follow one branch to exhaustion, marking visited nodes, then backtrack. Each launch from an unvisited node is one component.
GraphsO(V + E)New19 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
connected components
number of islands
cycle detection
path existence
The template
Get this into muscle memory, then adapt the condition per problem.
function dfs(r: number, c: number) {
if (out(r, c) || grid[r][c] !== 1) return;
grid[r][c] = 0;
for (const [dr, dc] of DIRS) dfs(r + dr, c + dc);
} Watch Depth First SearchIf you are stuck
The generic hint ladder for this pattern, in order.
- 1A grid is a graph where neighbours are the four adjacent cells.
- 2Sinking visited land avoids a separate visited matrix.
- 3Count how many times you start a fresh traversal.
Drill it
Every problem in the bank that uses this pattern.
0 / 19 solved