4.7 Number of Islands

4.7.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 200
• Difficulty: Medium
• URL: https://leetcode.com/problems/lc-number-of-islands/
• Tags: Grind 75, Blind 75, NeetCode 150
• Techniques: Depth First Search, Matrix

4.7.2 Description

Given a grid of '1' (land) and '0' (water), count the number of islands where islands are connected horizontally or vertically.

4.7.3 Examples

Input:
11110
11010
11000
00000
Output: 1

4.7.4 Constraints

• 1 <= rows, cols <= 300

4.7.5 Solution - Flood Fill

4.7.5.1 Walkthrough

Scan every cell. Upon encountering a '1', increment the island count and perform DFS/BFS to mark the entire island as visited (turn to '0' or another marker). Continue scanning until all land is processed.

4.7.5.2 Analysis

• Time Complexity: O(rows * cols)
• Space Complexity: O(rows * cols) recursion in worst case

4.7.5.3 Implementation Steps

1. Initialize count = 0.
2. For each cell:
   • If it is '1', run DFS that changes it and its connected neighbors to '0', and increment count.
3. Return count.

4.7.5.4 Code - Java

public int numIslands(char[][] grid) {
    int rows = grid.length;
    int 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') {
                islands++;
                flood(grid, r, c);
            }
        }
    }

    return islands;
}

private void flood(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') {
        return;
    }

    grid[r][c] = '0';
    flood(grid, r - 1, c);
    flood(grid, r + 1, c);
    flood(grid, r, c - 1);
    flood(grid, r, c + 1);
}