leetcode-200 Number of Islands

[200] Number of Islands

Key Concept: Connected Components via DFS/BFS - Each island is a connected component of '1's. Use DFS or BFS to mark all cells of an island as visited, then count how many times we initiate a new search.

Pattern: This is the fundamental pattern for finding connected components in a grid graph.

# Given an m x n 2D binary grid which represents a map of '1's (land) and
# '0's (water), return the number of islands.
# An island is surrounded by water and is formed by connecting adjacent lands
# horizontally or vertically.
#
# Example 1:
# Input: grid = [
#   ["1","1","1","1","0"],
#   ["1","1","0","1","0"],
#   ["1","1","0","0","0"],
#   ["0","0","0","0","0"]
# ]
# Output: 1
#
# Example 2:
# Input: grid = [
#   ["1","1","0","0","0"],
#   ["1","1","0","0","0"],
#   ["0","0","1","0","0"],
#   ["0","0","0","1","1"]
# ]
# Output: 3
#
# Constraints:
# m == grid.length
# n == grid[i].length
# 1 <= m, n <= 300

class Solution:
    # Approach 1: DFS (Most Intuitive)
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        count = 0

        def dfs(r, c):
            # Boundary check and water check
            if (r < 0 or r >= rows or c < 0 or c >= cols or
                grid[r][c] == '0'):
                return

            # Mark as visited by changing to '0'
            grid[r][c] = '0'

            # Explore all 4 directions
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        # Iterate through grid
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    dfs(r, c)  # Mark entire island

        return count

    # Approach 2: BFS
    def numIslands2(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        from collections import deque
        rows, cols = len(grid), len(grid[0])
        count = 0
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def bfs(r, c):
            queue = deque([(r, c)])
            grid[r][c] = '0'

            while queue:
                row, col = queue.popleft()
                for dr, dc in directions:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < rows and 0 <= nc < cols and
                        grid[nr][nc] == '1'):
                        grid[nr][nc] = '0'
                        queue.append((nr, nc))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    bfs(r, c)

        return count

# Time Complexity: O(m * n) - visit each cell once
# Space Complexity: O(m * n) - recursion stack in worst case
#
# Pattern: Grid DFS/BFS for connected components
# This pattern applies to many similar problems!