Graph based

Question 1

What is the definition of Graph-Based?

Answer 1

Uses graph traversal (DFS/BFS) for connectivity.

**Use Case: ** Path finding, connected components.

Example: [Number of Islands]. Action: Verbalize use case aloud.

Question 2

What are the key steps in Graph-Based?

Answer 2

1. Build graph (adjacency list/matrix).
2. Traverse using DFS/BFS.
3. Track visited nodes.

Action: Explain steps for [Number of Islands] aloud.

Question 3

How does Graph-Based apply to [Number of Islands]?

Answer 3

Count distinct islands in grid. Use DFS to mark connected land cells.

Action: Verbalize solution logic aloud.

Question 4

What are the complexity and gotchas of Graph-Based?

Answer 4

Time: O(V+E) or O(m * n), Space: O(V).
Gotchas: Disconnected graphs, empty grid.

Action: List edge cases for [Number of Islands] aloud.

Question 5

Code example for Graphs (Number of islands).

Answer 5

```python
from typing import List
def num_islands(grid: List[List[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
def dfs(row: int, col: int) -> None:
if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != ‘1’:
return
grid[row][col] = ‘0’
dfs(row-1, col)
dfs(row+1, col)
dfs(row, col-1)
dfs(row, col+1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == ‘1’:
islands += 1
dfs(r, c)
return islands
~~~

Action: Sketch island grid on paper.