LeetEye LeetEye
Medium Graph Traversal ~5 min

Number of Islands

graphs number-of-islands

Problem

Given an m x n 2D binary grid 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. You may assume all four edges of the grid are all surrounded by water.

Examples

Example 1
Input: grid = [
Output: 1
Example 2
Input: grid = [
Output: 3
Key Insight

When you find a '1', mark the entire island (all connected '1's) as visited. Count how many times you start a new island.

Count connected components: for each unvisited '1', increment count and flood-fill to mark the entire island.

How to Approach This Problem

Pattern Recognition: When you see keywords like number of islands graphs, think Graph Traversal.

Step-by-Step Reasoning

1 An island is:
Answer: A connected group of '1's
Adjacent '1's (up/down/left/right) form one island.
2 Each '1' cell is:
Answer: A node with edges to adjacent '1's
Think of it as a graph. Nodes = land cells. Edges = adjacency.
3 To count islands, we:
Answer: Count connected components of '1's
Each connected component = one island.
4 We can use:
Answer: Any of the above
All three work. DFS is simplest. Union-Find is elegant for component counting.
5 To avoid counting the same island twice:
Answer: Either A or B
Both work. In-place saves space but modifies input.
6 We increment island count when:
Answer: Both B and C
We increment when starting a new island (unvisited '1'). This is also when we finish that we've counted it.

Solution

def numIslands(grid: List[List[str]]) -> int:
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != &#039;1':
            return
        
        grid[r][c] = &#039;0'  # Mark visited
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == &#039;1':
                count += 1
                dfs(r, c)
    
    return count

Complexity Analysis

Time O(m × n)
Space O(m × n)

Master This Pattern

Build intuition with interactive MCQs. Practice Graph Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye