LeetCode Solutions Blog

Number of Islands

Number: 200

Difficulty: Medium

Paid? No

Problem Description

Given an m x n 2D binary grid where "1" represents land and "0" represents water, the task is to count the number of islands. An island is formed by connecting adjacent lands horizontally or vertically, and all four edges of the grid are surrounded by water.

Key Insights

Use graph traversal (DFS/BFS) to explore connected components of land.
Iterate over the matrix and start a traversal (e.g., DFS) when encountering an unvisited "1".
During traversal, mark visited cells to avoid duplicate counting.
Each DFS/BFS call completely explores one island.
Alternative approach can use Union Find to group connected lands.

Space and Time Complexity

Time Complexity: O(m * n), as each cell is visited at most once. Space Complexity: O(m * n) in the worst-case scenario due to recursion stack (DFS) or auxiliary data structures.

Solution

We solve the problem using a DFS-based approach. The algorithm iterates over each cell in the grid; when a "1" (land) is encountered, the DFS is initiated to mark the entire island (all connected "1"s) as visited (by setting them to "0"). This prevents recounting the same island. The island count is incremented each time a new island is discovered and fully explored.

Code Solutions

# Function to count the number of islands in the grid
def numIslands(grid):
    # If the grid is empty, return 0
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    islands = 0

    # Depth-First Search helper to mark the entire island as visited
    def dfs(r, c):
        # Check if the current cell is out of bounds or water
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == "0":
            return
        # Mark the cell as visited by setting it to water
        grid[r][c] = "0"
        # Explore all four adjacent cells (up, down, left, right)
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    
    # Iterate over every cell in the grid
    for r in range(rows):
        for c in range(cols):
            # If a land cell is found, conduct DFS to visit the entire island
            if grid[r][c] == "1":
                islands += 1
                dfs(r, c)
    
    return islands