LeetCode 200: Number of Islands Solution in Python Explained

Problem Statement

In LeetCode 200, you’re given a 2D binary grid grid:

• grid[i][j] is either '1' (land) or '0' (water).
• Rows m and columns n.

Your task is to return the number of islands, where:

• An island is a group of connected '1's (4-directionally: up, down, left, right).
• Islands are surrounded by water or grid edges.

This differs from tree traversal like LeetCode 199: Binary Tree Right Side View, focusing on grid connectivity rather than level-order views.

Constraints

• m == grid.length
• n == grid[i].length
• 1 ≤ m, n ≤ 300
• grid[i][j] is '0' or '1'.

Example

Let’s see some cases:

Copy codeInput: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1
Explanation: One island (top-left connected 1s).

Copy codeInput: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3
Explanation: Three islands: top-left, middle, bottom-right.

Copy codeInput: grid = [["1"]]
Output: 1
Explanation: Single land cell is one island.

These examples show we’re counting distinct land groups.

Understanding the Problem

How do you solve LeetCode 200: Number of Islands in Python? Take grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]. We need to count 3 islands:

• Top-left: 4 connected 1s.
• Middle: 1 1.
• Bottom-right: 2 connected 1s.

Brute-forcing by checking all cells and their connections is inefficient; we need a graph traversal approach (DFS or BFS) to mark visited land and count islands. This isn’t a robbery optimization like LeetCode 198: House Robber; it’s about grid exploration. We’ll use: 1. Depth-First Search with Marking: O(mn) time, O(1) space—our best solution (modifies grid). 2. Breadth-First Search with Queue: O(mn) time, O(m*n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Depth-First Search with Marking Approach

Explanation

Depth-First Search with Marking counts islands by:

• Iterating through each cell in the grid.
• When a '1' is found, increment island count and use DFS to:
• Mark all connected '1's as visited (e.g., change to '0').
• Explore 4 directions (up, down, left, right).
• Continue until all cells are checked.

This achieves O(m*n) time (visit each cell once), O(1) space (uses recursion stack, modifies grid in-place), and efficiency by avoiding extra data structures, making it optimal for this problem.

For [["1","1","0"],["1","0","0"]], DFS marks connected 1s, counts 1 island.

Step-by-Step Example

Example 1: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]

Goal: Return 3.

• Step 1: Initialize.
• count = 0, grid unchanged.
• Step 2: Iterate grid.
• (0,0) = '1': count = 1, DFS:
• Mark (0,0) → '0'.
• Down (1,0) = '1' → '0'.
• Right (0,1) = '1' → '0'.
• Down (1,1) = '1' → '0'.
• Grid: ["0","0","0","0","0"],["0","0","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]].
• (0,1) to (1,4): All '0', skip.
• (2,2) = '1': count = 2, DFS:
• Mark (2,2) → '0'.
• No adjacent '1's.
• Grid: ["0","0","0","0","0"],["0","0","0","0","0"],["0","0","0","0","0"],["0","0","0","1","1"]].
• (3,3) = '1': count = 3, DFS:
• Mark (3,3) → '0'.
• Right (3,4) = '1' → '0'.
• Grid: ["0","0","0","0","0"],["0","0","0","0","0"],["0","0","0","0","0"],["0","0","0","0","0"]].
• Step 3: Finish.
• All '1's marked, count = 3.
• Finish: Return 3.

Example 2: grid = [["1","1","1"],["0","1","0"],["1","1","1"]]

Goal: Return 1.

• Step 1: count = 0.
• Step 2: (0,0) = '1':
• count = 1, DFS marks all connected '1's → all '0'.
• Grid: all zeros after one DFS.
• Step 3: No more '1's, return 1.

How the Code Works (Depth-First Search with Marking) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef numIslands(grid: list[list[str]]) -> int:
    # Line 1: Handle empty grid
    if not grid:
        # No rows (e.g., [])
        return 0

    # Line 2: Initialize variables
    m, n = len(grid), len(grid[0])
    # Rows and cols (e.g., 4, 5)
    count = 0
    # Island count (e.g., 0)

    # Line 3: DFS helper function
    def dfs(i: int, j: int) -> None:
        # Mark and explore connected 1s
        if (i < 0 or i >= m or 
            j < 0 or j >= n or 
            grid[i][j] == "0"):
            # Out of bounds or water (e.g., i=-1)
            return
        grid[i][j] = "0"  # Mark visited (e.g., 1 → 0)
        dfs(i-1, j)  # Up
        dfs(i+1, j)  # Down
        dfs(i, j-1)  # Left
        dfs(i, j+1)  # Right

    # Line 4: Iterate grid
    for i in range(m):
        # Rows (e.g., 0 to 3)
        for j in range(n):
            # Columns (e.g., 0 to 4)
            if grid[i][j] == "1":
                # Found land (e.g., (0,0))
                count += 1
                # New island (e.g., 1)
                dfs(i, j)
                # Mark all connected 1s (e.g., top-left island)

    # Line 5: Return island count
    return count
    # e.g., 3

This detailed breakdown clarifies how DFS with marking efficiently counts islands.

Alternative: Breadth-First Search with Queue Approach

Explanation

Breadth-First Search with Queue counts islands by:

• Using a queue to explore connected '1's level by level.
• Marking visited cells (e.g., to '0').
• Incrementing count for each new island.

It’s a practical alternative, O(mn) time (visit each cell), O(mn) space (queue can hold entire grid in worst case), and level-order, though uses more space than DFS.

For same grid:

• BFS marks islands similarly, counts 3.

Step-by-Step Example (Alternative)

For [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]:

• (0,0): Queue explores all top-left '1's → mark, count=1.
• (2,2): Queue marks single '1', count=2.
• (3,3): Queue marks two '1's, count=3.
• Finish: Return 3.

How the Code Works (BFS)

Copy codefrom collections import deque

def numIslandsBFS(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    count = 0
    queue = deque()

    for i in range(m):
        for j in range(n):
            if grid[i][j] == "1":
                count += 1
                queue.append((i, j))
                while queue:
                    x, y = queue.popleft()
                    if grid[x][y] == "0":
                        continue
                    grid[x][y] = "0"
                    for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1":
                            queue.append((nx, ny))

    return count

Complexity

• Depth-First Search with Marking:
• Time: O(m*n) – visit each cell.
• Space: O(1) – recursion stack (or O(m*n) worst case).
• Breadth-First Search with Queue:
• Time: O(m*n) – visit each cell.
• Space: O(m*n) – queue size.

Efficiency Notes

Depth-First Search with Marking is the best solution with O(mn) time and O(1) space (modifying grid), offering simplicity and minimal memory—Breadth-First Search with Queue matches time complexity but uses O(mn) space, making it less space-efficient but equally effective.

Key Insights

• DFS: Recursive marking.
• BFS: Queue-based exploration.
• Connected: 4-directional.

Additional Example

For [["1","0"],["0","1"]]:

• Goal: 2.
• DFS: Two separate '1's → 2 islands.

Edge Cases

• Empty Grid: 0.
• Single Cell: 1 or 0.
• All Water: 0.

Both solutions handle these well.

Final Thoughts

LeetCode 200: Number of Islands in Python is a classic grid traversal challenge. The Depth-First Search with Marking solution excels with its space efficiency and clarity, while Breadth-First Search with Queue offers a level-order alternative. Want more? Try LeetCode 695: Max Area of Island for island sizing or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 200 on LeetCode with [["1","1","0"],["1","0","0"]], aiming for 1—test your skills now!