Island (Matrix Traversal): Explaination and code in Python, Java, C++, and JavaScript

Matrix traversal involves systematically visiting each cell in a two-dimensional grid, which is crucial for solving various grid-related problems. These problems often include finding connected components, identifying paths, or counting clusters. Understanding matrix traversal is key to addressing scenarios such as island counting, where connected 'land' cells form individual islands.

Matrix traversal is used to solve problems related to grids, such as finding connected components or islands.

Real World Problem: Counting Groups of Trees in a Park

Imagine you're in charge of maintaining a park, and you have a map of the park. Each cell in the map represents a small plot of land. Some plots have trees, represented by 1, while others are empty, represented by 0.

You need to count how many groups of connected trees there are in the park. A group of trees is defined as a cluster of 1s that are connected either horizontally or vertically (but not diagonally). Your task is to find out how many separate groups of trees exist in the park.

Example Park Map:

1 1 0 0
1 0 0 1
0 0 1 1

In this example:

• The first group of trees consists of two connected 1s in the top-left corner (forming one group).
• The second group is a single 1 in the second row, fourth column (a separate group).
• The third group consists of two connected 1s in the bottom-right corner (another separate group).

Steps to count the groups:

1. Start from the top-left cell. It's a 1, so it’s part of a tree group. Mark it as visited and move to the next adjacent cell. Keep visiting all connected 1s until the whole group is marked.
2. Move to the next unvisited cell, find another 1, and mark that as part of a new group.
3. Repeat this process until you’ve checked all cells in the map.

After visiting all the cells, you will find 3 separate tree groups.

Result:

The number of tree groups (islands) in the park is 3.

This simplified example shows how the problem of counting connected components (like groups of trees) can be mapped to the island-counting problem in a way that's easier to understand. The idea of "groups of trees" should make the concept of connected land cells (1s) more intuitive for beginners.

Let me know if you need further clarification!

Example Problem:

Find the number of islands in a grid (where '1' represents land and '0' represents water). An island is defined as a group of connected '1's (land cells) surrounded by '0's (water). Connectivity can be horizontal or vertical, but not diagonal.

Example Grid:

1 1 0 0
1 0 0 1
0 0 1 1

In the above grid, there are three islands:

1. The first two '1's in the top-left corner.
2. The single '1' in the second row, fourth column.
3. The two '1's in the bottom-right corner.

Python:

from collections import deque

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = set()

    def bfs(r, c):
        q = deque([(r, c)])
        visited.add((r, c))
        while q:
            row, col = q.popleft()
            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and 0 <= nc < cols and
                        (nr, nc) not in visited and grid[nr][nc] == '1'):
                    visited.add((nr, nc))
                    q.append((nr, nc))

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                bfs(r, c)
                islands += 1

    return islands

# Example usage
grid = [
    ["1", "1", "0", "0"],
    ["1", "0", "0", "1"],
    ["0", "0", "1", "1"],
]
print(num_islands(grid))  # Output: 3

C++:

#include <vector>
#include <queue>
#include <utility>
#include <iostream>

using namespace std;

void bfs(vector<vector<char>>& grid, int r, int c) {
    int rows = grid.size(), cols = grid[0].size();
    queue<pair<int, int>> q;
    q.push({r, c});
    grid[r][c] = '0';

    vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    while (!q.empty()) {
        auto [row, col] = q.front();
        q.pop();
        for (auto [dr, dc] : directions) {
            int nr = row + dr, nc = col + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
                grid[nr][nc] = '0';
                q.push({nr, nc});
            }
        }
    }
}

int numIslands(vector<vector<char>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    int islands = 0;

    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == '1') {
                bfs(grid, r, c);
                ++islands;
            }
        }
    }

    return islands;
}

int main() {
    vector<vector<char>> grid = {
        {'1', '1', '0', '0'},
        {'1', '0', '0', '1'},
        {'0', '0', '1', '1'},
    };
    cout << numIslands(grid) << endl; // Output: 3
    return 0;
}

Java:

import java.util.*;

public class Main {
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int rows = grid.length, cols = grid[0].length;
        int islands = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    bfs(grid, r, c);
                    islands++;
                }
            }
        }
        return islands;
    }

    private static void bfs(char[][] grid, int r, int c) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{r, c});
        grid[r][c] = '0';

        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (!q.isEmpty()) {
            int[] pos = q.poll();
            for (int[] d : directions) {
                int nr = pos[0] + d[0], nc = pos[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
                    grid[nr][nc] = '0';
                    q.offer(new int[]{nr, nc});
                }
            }
        }
    }

    public static void main(String[] args) {
        char[][] grid = {
            {'1', '1', '0', '0'},
            {'1', '0', '0', '1'},
            {'0', '0', '1', '1'},
        };
        System.out.println(numIslands(grid)); // Output: 3
    }
}

JavaScript:

function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;

    const rows = grid.length;
    const cols = grid[0].length;

    function bfs(r, c) {
        const queue = [[r, c]];
        grid[r][c] = '0';

        const directions = [
            [0, 1], [1, 0], [0, -1], [-1, 0]
        ];

        while (queue.length > 0) {
            const [row, col] = queue.shift();
            for (const [dr, dc] of directions) {
                const nr = row + dr;
                const nc = col + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
                    grid[nr][nc] = '0';
                    queue.push([nr, nc]);
                }
            }
        }
    }

    let islands = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') {
                bfs(r, c);
                islands++;
            }
        }
    }

    return islands;
}

// Example usage
const grid = [
    ['1', '1', '0', '0'],
    ['1', '0', '0', '1'],
    ['0', '0', '1', '1']
];
console.log(numIslands(grid)); // Output: 3