💬 Discord
Sign In
NeetCode #562LC-200MediumGraphsBlind 75NC 150NC 250
← Back to All Problems

#562 · #200 · Number of Islands(岛屿数量)

📌 Problem Statement & Constraints

Given an m x n 2D binary grid where '1' is land and '0' is water, return the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically. Constraints: 1 <= m, n <= 300.

💡 Core Algorithmic Approaches

  1. Scan the grid; each time an unvisited '1' is found, it starts a new island.
  2. Flood-fill from that cell, marking every connected land cell as visited.
  3. Marking in place (setting '1' to '0') avoids allocating a separate visited set.
  4. Each cell is visited at most once across the whole scan, so the total is O(m*n).

💻 Benchmark Python3 Implementation

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0

        def dfs(r: int, c: int) -> None:
            if not (0 <= r < m and 0 <= c < n) or grid[r][c] != "1":
                return
            grid[r][c] = "0"               # mark visited in place
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    count += 1             # a new island
                    dfs(i, j)
        return count


# BFS variant: avoids deep recursion on large grids
class Solution2:
    def numIslands(self, grid: List[List[str]]) -> int:
        from collections import deque
        m, n = len(grid), len(grid[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] != "1":
                    continue
                count += 1
                grid[i][j] = "0"
                q = deque([(i, j)])
                while q:
                    r, c = q.popleft()
                    for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1":
                            grid[nr][nc] = "0"
                            q.append((nr, nc))
        return count

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): each cell is visited at most once.
💾 Space Complexity
O(m * n) for the recursion stack in the worst case (an all-land grid).

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the bounds check before indexing: the guard must come first.
  • Counting inside the DFS: the count belongs to the outer scan, once per island.
  • Using a separate visited set: workable but O(m*n) extra memory; in-place marking is free.
  • Recursing on a 300x300 all-land grid: the depth can reach 90 000, exceeding Python's default limit -- the BFS variant is safer.