200. Number of Islands
https://workat.tech/problem-solving/practice/number-of-islands
Intuition
Find number of disconnected components
DFS is more appropriate
DFS -> Start DFS whenever you see a 1, sink ie., convert 1 to 0 as you progress through DFS, this is a proxy to visited set, and prevents coming back
BFS -> Similar, start BFS whenever you see a 1, convert 1 to 0 before you offer to q, this is a proxy to visited set, and prevents coming back
---
Time - O(R * C)
Space - O(R * C) - recursion stack / q size
---
---
Given a 2d grid map of
'1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.Example 1:
Input: 11110 11010 11000 00000 Output: 1
Example 2:
Input: 11000 11000 00100 00011 Output: 3---
Intuition
Find number of disconnected components
DFS is more appropriate
DFS -> Start DFS whenever you see a 1, sink ie., convert 1 to 0 as you progress through DFS, this is a proxy to visited set, and prevents coming back
BFS -> Similar, start BFS whenever you see a 1, convert 1 to 0 before you offer to q, this is a proxy to visited set, and prevents coming back
---
Time - O(R * C)
Space - O(R * C) - recursion stack / q size
---
---