Problem Statement

Given a binary matrix where 1 represents land and 0 represents water, count the number of islands. A island is formed by adjacent lands connected horizontally or vertically. The matrix is surrounded by water on all sides.

Input Format

• First line: Two integers N (rows) and M (columns)
• Next N lines: M space-separtaed integers (0 or 1)

Output

A single integer representing the island count

Solution Approaches

Depth-First Search (DFS)

def count_islands_dfs(matrix):
    if not matrix:
        return 0
    
    rows, cols = len(matrix), len(matrix[0])
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    count = 0
    
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 1 and not visited[i][j]:
                count += 1
                dfs(matrix, visited, i, j)
    return count

def dfs(matrix, visited, x, y):
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    visited[x][y] = True
    
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):
            if matrix[nx][ny] == 1 and not visited[nx][ny]:
                dfs(matrix, visited, nx, ny)

Breadth-First Search (BFS)

from collections import deque

def count_islands_bfs(matrix):
    if not matrix:
        return 0
    
    rows, cols = len(matrix), len(matrix[0])
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    count = 0
    
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 1 and not visited[i][j]:
                count += 1
                bfs(matrix, visited, i, j)
    return count

def bfs(matrix, visited, x, y):
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    queue = deque([(x,y)])
    visited[x][y] = True
    
    while queue:
        cx, cy = queue.popleft()
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):
                if matrix[nx][ny] == 1 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

Key Implementation Notes

1. DFS vs BFS: Both approaches work similarly by marking connected components
2. Visited Tracking: Crucial too mark nodes when they're first discovered to avoid revisiting
3. Boundary Checks: Essential to prevent index errors when checking adjacent cells
4. Performance: Both algorithms have O(N*M) time complexity where N and M are matrix dimensions