# LeetCode 200: Number of Islands

## Problem Restatement

We are given an `m x n` grid.

Each cell is one of two characters:

| Character | Meaning |
|---|---|
| `"1"` | Land |
| `"0"` | Water |

We need to count how many islands exist in the grid.

An island is a group of land cells connected horizontally or vertically. Diagonal connection does not count. The official problem asks for the number of islands in a binary grid of land and water.

## Input and Output

| Item | Meaning |
|---|---|
| Input | 2D grid of `"1"` and `"0"` characters |
| Output | Number of islands |
| Connected directions | Up, down, left, right |
| Diagonal connection | Does not count |
| Boundary assumption | Grid edges are surrounded by water |

Example function shape:

```python
def numIslands(grid: list[list[str]]) -> int:
    ...
```

## Examples

Example 1:

```python
grid = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"],
]
```

All land cells belong to one connected group.

Output:

```python
1
```

Example 2:

```python
grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"],
]
```

There are three separate islands.

Output:

```python
3
```

## First Thought: Scan Every Cell

We can scan the whole grid from top-left to bottom-right.

When we see water, we ignore it.

When we see land, we have found an island.

But that land cell may connect to many other land cells. We must mark the whole island as visited, otherwise we may count the same island again later.

So the process is:

1. Find an unvisited land cell.
2. Count one new island.
3. Visit all land cells connected to it.
4. Continue scanning.

This is a connected components problem on a grid graph.

## Key Insight

Each land cell is like a graph node.

Two land cells are connected if they are adjacent in one of four directions:

```text
up, down, left, right
```

When we find a `"1"`, we use DFS or BFS to visit the entire connected component.

To avoid extra `visited` memory, we can modify the grid in-place by turning visited land into water:

```python
grid[r][c] = "0"
```

This is often called sinking the island.

Once an island is sunk, it cannot be counted again.

## Algorithm

1. Let `rows = len(grid)` and `cols = len(grid[0])`.
2. Initialize `islands = 0`.
3. Scan every cell `(r, c)`.
4. If `grid[r][c] == "1"`:
   - Increase `islands` by `1`.
   - Run DFS from `(r, c)` to mark the whole island as visited.
5. Return `islands`.

## DFS Procedure

For a cell `(r, c)`:

1. If the cell is outside the grid, stop.
2. If the cell is water, stop.
3. Mark it as visited by changing it to `"0"`.
4. Visit its four neighbors:
   - `(r + 1, c)`
   - `(r - 1, c)`
   - `(r, c + 1)`
   - `(r, c - 1)`

## Correctness

The main scan finds every cell in the grid.

When it reaches a land cell `"1"`, that cell has not been visited before, because visited land cells are changed to `"0"`.

So this cell must belong to a new island, and increasing the island count is correct.

The DFS visits exactly all land cells connected to the starting cell through horizontal or vertical moves. It changes all of them to `"0"`, so no cell from the same island can start another count later.

Every island has at least one land cell. The first unvisited land cell from that island encountered by the scan will count it once.

Therefore, every island is counted once, and no island is counted more than once.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(mn)` | Each grid cell is visited at most once |
| Space | `O(mn)` | DFS recursion stack can reach all cells in the worst case |

Here, `m` is the number of rows and `n` is the number of columns.

The grid itself is modified in-place, so the extra data structure space is only the recursion stack.

## Implementation

```python
class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        islands = 0

        def dfs(r: int, c: int) -> None:
            if r < 0 or r == rows or c < 0 or c == cols:
                return

            if grid[r][c] == "0":
                return

            grid[r][c] = "0"

            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    islands += 1
                    dfs(r, c)

        return islands
```

## Code Explanation

We store the grid dimensions:

```python
rows = len(grid)
cols = len(grid[0])
```

The answer starts at zero:

```python
islands = 0
```

The DFS first checks whether the cell is outside the grid:

```python
if r < 0 or r == rows or c < 0 or c == cols:
    return
```

Then it stops on water:

```python
if grid[r][c] == "0":
    return
```

If the cell is land, we mark it visited:

```python
grid[r][c] = "0"
```

Then we explore the four connected directions:

```python
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
```

The outer loops scan every cell:

```python
for r in range(rows):
    for c in range(cols):
```

When an unvisited land cell is found, we count one island and sink it:

```python
if grid[r][c] == "1":
    islands += 1
    dfs(r, c)
```

## Alternative Implementation With BFS

DFS recursion can be replaced with an explicit queue.

```python
from collections import deque

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        islands = 0

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def bfs(sr: int, sc: int) -> None:
            queue = deque([(sr, sc)])
            grid[sr][sc] = "0"

            while queue:
                r, c = queue.popleft()

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if nr < 0 or nr == rows or nc < 0 or nc == cols:
                        continue

                    if grid[nr][nc] == "0":
                        continue

                    grid[nr][nc] = "0"
                    queue.append((nr, nc))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    islands += 1
                    bfs(r, c)

        return islands
```

BFS avoids recursion depth issues and has the same time complexity.

## Testing

```python
def run_tests():
    s = Solution()

    grid = [
        ["1", "1", "1", "1", "0"],
        ["1", "1", "0", "1", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "0", "0", "0"],
    ]
    assert s.numIslands(grid) == 1

    grid = [
        ["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"],
    ]
    assert s.numIslands(grid) == 3

    grid = [["0"]]
    assert s.numIslands(grid) == 0

    grid = [["1"]]
    assert s.numIslands(grid) == 1

    grid = [
        ["1", "0", "1"],
        ["0", "1", "0"],
        ["1", "0", "1"],
    ]
    assert s.numIslands(grid) == 5

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| One large island | Checks connected land counting |
| Three islands | Main separated-islands example |
| Single water cell | No island |
| Single land cell | One island |
| Diagonal land cells | Confirms diagonal connection does not count |