Number Of Islands

---

Intuition

For each grid cell, check if it is land. If it is, then that land is guaranteed to be part of an island. Add all other land of that island, then increment the number of islands by one. This ensures that you have marked the land on that island and won’t run it again.

Complexity

Runtime

$O(MN)$

Space

$O(MN)$

Code

BFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
 
        def inbounds(r, c):
            return r >= 0 and c < n and r < m and c >= 0
 
        visited = set()
        def bfs(r, c):
            visited.add((r, c))
            q = deque()
            q.append((r, c))
            while q:
                x, y = q.popleft()
                for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if inbounds(i, j) and grid[i][j] == '1' and (i, j) not in visited:
                        visited.add((i, j))
                        q.append((i, j))
    
        res = 0
        for r in range(m):
            for c in range(n):
                if (r, c) not in visited and grid[r][c] == '1':
                    res += 1
                    bfs(r, c)
                
        return res

DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
 
        def _adj(x, y):
            res = []
            for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
                if (0 <= a < m and 0 <= b < n):
                    res.append((a, b))
            
            return res
 
        seen = set()
 
        @cache
        def dfs(x, y):
            seen.add((x, y))
 
            for a, b in _adj(x, y):
                if grid[a][b] == '1' and (a, b) not in seen:
                    dfs(a, b)
 
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1' and (i, j) not in seen:
                    res += 1
                    dfs(i, j)
 
        return res

Cards

START Basic Front: Number Of Islands Back: Keep track of neighbors you have encountered so far END

---

References

• Number Of Islands