Editorial: Number of Islands

1 Intuition

Each island is a connected component in the grid. We can use DFS or BFS to explore each component. When we find a land cell ('1') that's not yet visited, we increment the count and explore the entire island.

2 Approach

1. Create a visited set or mark cells as visited 2. Iterate through all cells: - If cell is land and not visited - Increment island count - Use DFS/BFS to mark all connected land cells as visited 3. Return island count

3 Complexity Analysis

**Time Complexity:** O(m × n) - visit each cell once **Space Complexity:** O(m × n) - visited array/set Both DFS and BFS have same time/space complexity.

4 Solution Code

def numIslands(grid):
    if not grid:
        return 0
    count = 0
    visited = set()
    def dfs(r, c):
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
            return
        if (r, c) in visited or grid[r][c] == "0":
            return
        visited.add((r, c))
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == "1" and (i, j) not in visited:
                count += 1
                dfs(i, j)
    return count

int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    int count = 0;
    vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
    function<void(int, int)> dfs = [&](int r, int c) {
        if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() ||
            visited[r][c] || grid[r][c] == '0') return;
        visited[r][c] = true;
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
    };
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == '1' && !visited[i][j]) {
                count++;
                dfs(i, j);
            }
        }
    }
    return count;
}

5 Code Walkthrough

For grid = [["1","1","0"],["0","1","0"],["1","0","1"]]: - (0,0): Find unvisited "1", count=1, DFS marks (0,0), (0,1), (1,1) - (2,0): Find unvisited "1", count=2, DFS marks (2,0) - (2,2): Find unvisited "1", count=3, DFS marks (2,2) Result: 3 islands