# Number of Islands

## Question ([LC.200](https://leetcode.com/problems/number-of-islands/?tab=Description))

> Given a 2D grid consists of "1"s and "0"s, count the number of connected "1"s.

An island ("1"s) can be connected vertically and horizontally. Assume all 4 edges are surrounded by water.

## Example

The given input is a `char[][]`.

```
11110
11010
11000
00000
```

Output: 1

```
11000
11000
00100
00011
```

Output: 1+1+1 = 3

## Analysis

This question is essentially searching connected components in a simple graph. We can solve it with either BFS or DFS. We prefer BFS over DFS because `1 1 1 1 1 ... 1` can overflow the call stack. Say we want to eat a hamburger. Do you want to eat normally by taking a couple bites around the side? Or do you want to keep biting in one direction until you reach the end of that direction? Sure both methods can finish the burger, but your mouth might get very full by choosing the second way.

## BFS Approach

```
for the graph
    if 1 then bfsConnected
bfsConnected
    if inBound and 1 offer to queue
    no need visited b/c we can change the grid
```

## BFS Code

```java
private class Pos {
    int row;
    int col;
    public Pos(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

int[] drow = new int[] {0, -1, 0, 1};
int[] dcol = new int[] {-1, 0, 1, 0};

private boolean inBound(char[][] grid, Pos pt) {
    int m = grid.length;
    int n = grid[0].length;
    if (pt.row < 0 || pt.row >= m) {
        return false;
    }
    if (pt.col < 0 || pt.col >= n) {
        return false;
    }
    return true;
}

public int numIslands(char[][] grid) {
    int landCount = 0;
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return landCount;
    }
    int m = grid.length;
    int n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                landCount++;
                bfsConnected(grid, new Pos(i,j));
            }
        }
    }
    return landCount;
}

private void bfsConnected(char[][] grid, Pos start) {
    // init queue
    Queue<Pos> queue = new LinkedList<>();
    queue.offer(start);
    grid[start.row][start.col] = '0';
    // bfs
    Pos current;
    while (!queue.isEmpty()) {
        current = queue.poll();
        // search its neighbors
        for (int p = 0; p < 4; p++) {
            Pos neighbor = new Pos(current.row + drow[p], current.col + dcol[p]);
            if (!inBound(grid, neighbor)) {
                continue;
            }
            if (grid[neighbor.row][neighbor.col] == '1') {
                queue.offer(neighbor);
                grid[neighbor.row][neighbor.col] = '0'; // visited
            }
        }  
    }
}
```

## Time Complexity

O(mn)

## DFS Approach

```java
private void dfsConnected(char[][] grid, Pos current) {
    // base
    if (!inBound(grid, current)) {
        return;
    }
    if (grid[current.row][current.col] == '0') {
        return;
    }
    // previsit
    grid[current.row][current.col] = '0'; // visited
    // dfs
    for (int p = 0; p < 4; p++) {
        Pos neighbor = new Pos(current.row + drow[p], current.col + dcol[p]);
        dfsConnected(grid, neighbor);
    }
}
```

## Follow Up #0

Only destroy the island if the number of 1s is less than k

* have a flag at the end of the path, if path\_length < k, give permission to destroy the island on the back back (backtracking) otherwise label it as red zone (label is -1 or something so we don't touch it). So we want to measure how long this subway is before we eat it backward. i.e. if it's 12in we don't want to eat it, label it red. But if it's 6in, then eat it backward.

## Follow Up #1

Count number of lakes

## Follow up #2

Measure the length of the seashore

## Number of Islands II (Union Find)

## Reference

Segmentfault [Number of Islands](https://segmentfault.com/a/1190000003753307) by Ethan Li


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/graph-search/search-in-a-grid/number-of-islands.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.