Python Program to Find Number of Islands

You can find the number of islands in a grid by using a depth-first search (DFS) to explore connected land cells, marking visited cells with a function like def num_islands(grid): that counts islands by traversing all cells and running DFS on unvisited land.

Examples

Input[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]

Output3

Input[["1","1","1"],["0","1","0"],["1","1","1"]]

Output1

Input[["0","0","0"],["0","0","0"],["0","0","0"]]

Output0

How to Think About It

Think of the grid as a map where '1' means land and '0' means water. To find islands, scan each cell. When you find land that is not visited, start exploring all connected land cells around it using up, down, left, and right moves. Mark these cells as visited so you don't count them again. Each new unvisited land cell you find starts a new island count.

Algorithm

1

Initialize a count for islands to zero.

2

Loop through each cell in the grid.

3

If the cell is land ('1') and not visited, increase island count by one.

4

Use DFS to mark all connected land cells as visited.

5

Continue until all cells are checked.

6

Return the island count.

Code

python

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False]*cols for _ in range(rows)]

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols:
            return
        if grid[r][c] == '0' or visited[r][c]:
            return
        visited[r][c] = True
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1' and not visited[i][j]:
                dfs(i, j)
                count += 1
    return count

# Example usage
example_grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
print(num_islands(example_grid))

Output

3

Dry Run

Let's trace the example grid [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]] through the code.

1

Start scanning grid

At cell (0,0), value is '1' and not visited, start DFS and increment count to 1.

2

DFS marks connected land

Mark (0,0), (0,1), (1,0), (1,1) as visited by exploring neighbors.

3

Continue scanning

Cells (0,2) to (1,4) are water or visited, skip.

4

Find next island

At cell (2,2), value is '1' and not visited, start DFS and increment count to 2.

5

Mark single cell island

Mark (2,2) as visited.

6

Find last island

At cell (3,3), value is '1' and not visited, start DFS and increment count to 3.

7

Mark connected land

Mark (3,3) and (3,4) as visited.

8

End scan

All cells checked, return count 3.

Step	Action	Island Count
1	Found land at (0,0), start DFS	1
2	Mark connected land (0,0),(0,1),(1,0),(1,1)	1
3	Skip water/visited cells	1
4	Found land at (2,2), start DFS	2
5	Mark (2,2) visited	2
6	Found land at (3,3), start DFS	3
7	Mark (3,3),(3,4) visited	3
8	All cells checked, return count	3

Why This Works

Step 1: Why use DFS?

DFS helps explore all connected land cells from a starting point, ensuring we count one island fully before moving on.

Step 2: Marking visited cells

Marking cells as visited prevents counting the same land multiple times and avoids infinite loops.

Step 3: Counting islands

Each time we find unvisited land, it means a new island, so we increase the count.

Alternative Approaches

Breadth-First Search (BFS)

python

from collections import deque

def num_islands_bfs(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False]*cols for _ in range(rows)]

    def bfs(r, c):
        queue = deque([(r, c)])
        visited[r][c] = True
        while queue:
            x, y = queue.popleft()
            for nx, ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny] and grid[nx][ny] == '1':
                    visited[nx][ny] = True
                    queue.append((nx, ny))

    count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1' and not visited[i][j]:
                bfs(i, j)
                count += 1
    return count

# BFS example usage
example_grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
print(num_islands_bfs(example_grid))

BFS uses a queue and explores neighbors level by level; it is easier to understand for some but uses extra memory for the queue.

Union-Find (Disjoint Set)

python

class UnionFind:
    def __init__(self, grid):
        self.count = 0
        self.parent = {}
        self.rank = {}
        rows, cols = len(grid), len(grid[0])
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    self.parent[(r,c)] = (r,c)
                    self.rank[(r,c)] = 0
                    self.count += 1

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            self.count -= 1


def num_islands_union_find(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(grid)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                for nr, nc in [(r+1,c),(r,c+1)]:
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        uf.union((r,c), (nr,nc))
    return uf.count

# Union-Find example usage
example_grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
print(num_islands_union_find(example_grid))

Union-Find efficiently merges connected land cells and counts distinct sets; it is faster for large grids but more complex to implement.

Complexity: O(m*n) time, O(m*n) space

Time Complexity

The algorithm visits each cell once and explores its neighbors, so it runs in O(m*n) where m and n are grid dimensions.

Space Complexity

Extra space is used for the visited matrix and recursion stack or queue, which can be O(m*n) in the worst case.

Which Approach is Fastest?

DFS and BFS have similar time and space complexity; Union-Find can be faster for large grids but requires more complex code.

Approach	Time	Space	Best For
DFS	O(m*n)	O(m*n)	Simple and intuitive for small to medium grids
BFS	O(m*n)	O(m*n)	Easier to understand for some, uses queue
Union-Find	O(m*n)	O(m*n)	Large grids, faster union operations, complex implementation