DFS And BFS
Thinking Patterns - DFS v.s. Backtrack
Problems - Islands Problems
| Problems | Possible Solutions | Key Points | Code | Similar Problems | Comments |
|---|---|---|---|---|---|
| 200. Number of Islands | dfs, bfs | code | |||
| 1254. Number of Closed Islands | dfs, bfs | code | |||
| 1905. Count Sub Islands | dfs, bfs, union-find | code | 1992 | ||
| 1020. Number of Enclaves | dfs, bfs | code | |||
| 694. Number of Distinct Islands | dfs, bfs | code | |||
| 695. Max Area of Island | dfs, bfs | code | |||
| - |
Key Points
- 694
How to present the shape of islands with
BFSandDFS?
Complexity Analyze
- 200.
Time Complexity
- O(N+4N) = O(N) N = m*n
- Loop all the node outside, m*n
- Overall O(N)
Space Complexity
- For DFS, Recursive stack depth: worst at
O(N)- For BFS, Queue length: worst at
O(N)- Worst case example,
m=1, n = N, and all equals 1- Use
gridas visited, no extra spaces
- 1254, 1905, 1020, 694
Similar as 200