Graph

Number of Islands

DFS/BFS on grid:

1. Iterate all cells

2. If land ('1'), run DFS/BFS to mark entire island as visited

3. Increment count

   Turn visited land into water or use visited set

Flood Fill

DFS/BFS from starting pixel:

1. If new color == original, return

2. Traverse neighbors (4 directions)

3. Recolor all connected same-color cells

01 Matrix (Multi-source BFS)

BFS from all 0s:

1. Push all 0 cells into queue

2. Initialize others as ∞

3. BFS outward, updating distance = prev + 1

   Shortest distance to nearest 0

Rotting Oranges (Multi-source BFS)

BFS from all rotten oranges:

1. Push all rotten (2) into queue

2. Count fresh oranges

3. Each level = 1 minute, rot neighbors

4. Decrease fresh count

5. If fresh becomes 0 → return minutes, else -1

Clone Graph

DFS/BFS + hashmap:

1. Map original node → cloned node

2. For each node, clone neighbors recursively

3. Avoid revisiting using map

   Graph copy via mapping

Pacific Atlantic Water Flow

Reverse DFS/BFS:

1. Start from ocean edges (Pacific & Atlantic separately)

2. Move inward only to higher/equal heights

3. Mark reachable cells for each ocean

4. Intersection = answer

Course Schedule

Cycle detection in directed graph:

1. Build adjacency list

2. DFS with 3 states: unvisited, visiting, visited

3. If visiting node seen again → cycle

4. If no cycle → possible to finish

   Topological sort concept

Max Area of Island

DFS/BFS on grid:

1. Iterate all cells

2. If land (1), run DFS/BFS to explore connected island

3. Count number of cells in this island

4. Track maximum area seen

   Mark visited by turning land to water or using visited set