# LeetCode 463: Island Perimeter

## Problem Restatement

We are given a rectangular grid.

Each cell is either:

```python
1  # land
0  # water
```

The grid contains exactly one island. Land cells connect horizontally or vertically, not diagonally. The grid is surrounded by water, and the island has no lakes. We need to return the perimeter of the island.

A land cell is a square with side length `1`.

So one isolated land cell has perimeter:

```python
4
```

When two land cells touch, they share one edge. That shared edge is no longer part of the outside perimeter.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A 2D grid of `0`s and `1`s |
| Output | The island perimeter |
| Land | `1` |
| Water | `0` |
| Connection | Horizontal and vertical only |
| Grid size | At most `100 x 100` |

Function shape:

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

## Examples

Example 1:

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

The answer is:

```python
16
```

This is the standard example from the problem statement.

Example 2:

```python
grid = [[1]]
```

There is one land cell and no neighboring land.

Its perimeter is:

```python
4
```

Example 3:

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

There is one land cell touching water on the right and grid boundary on the other sides.

The perimeter is:

```python
4
```

## First Thought: Count Exposed Sides

The perimeter is made of land-cell edges that touch water or the grid boundary.

So for each land cell, we can inspect its four directions:

```python
up
down
left
right
```

For each direction:

1. If the neighbor is outside the grid, add `1`.
2. If the neighbor is water, add `1`.
3. If the neighbor is land, add `0`.

This is direct and easy to reason about.

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

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

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    continue

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

                    if nr < 0 or nr == rows or nc < 0 or nc == cols:
                        perimeter += 1
                    elif grid[nr][nc] == 0:
                        perimeter += 1

        return perimeter
```

This works because it counts exactly the outside edges of land cells.

## Problem With This Approach

This approach is already efficient.

It scans every cell once and checks four directions.

The time complexity is:

```python
O(rows * cols)
```

That is optimal because we may need to inspect the whole grid.

However, there is an even simpler counting formula.

Each land cell starts with `4` edges.

Whenever two land cells are adjacent, they share one edge.

That shared edge removes `2` from the total perimeter: one edge from the first cell and one edge from the second cell.

## Key Insight

For every land cell:

```python
perimeter += 4
```

Then for each shared edge between two land cells:

```python
perimeter -= 2
```

To avoid counting the same shared edge twice, we only check two directions for each land cell:

```python
down
right
```

If the cell below is land, subtract `2`.

If the cell to the right is land, subtract `2`.

This counts every adjacent land pair exactly once.

## Algorithm

Initialize:

```python
perimeter = 0
```

Loop through every cell.

If the current cell is water, skip it.

If it is land:

1. Add `4`.
2. If the cell below is land, subtract `2`.
3. If the cell to the right is land, subtract `2`.

Return `perimeter`.

## Walkthrough

Use a small grid:

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

There are two land cells.

Start:

```python
perimeter = 0
```

First land cell:

```python
perimeter += 4
```

It has a right neighbor that is also land, so:

```python
perimeter -= 2
```

Now:

```python
perimeter = 2
```

Second land cell:

```python
perimeter += 4
```

No right or down land neighbor.

Final:

```python
perimeter = 6
```

This is correct because a `1 x 2` rectangle has perimeter `6`.

## Correctness

Each land cell contributes four sides before considering neighboring land cells.

If two land cells are adjacent, the edge between them is internal. It cannot be part of the island's outside perimeter.

The algorithm subtracts `2` for each adjacent land pair: one side from each of the two cells.

By checking only the down and right neighbors, each adjacent land pair is counted exactly once.

Therefore, after all land cells are processed, the remaining count is exactly the number of land-cell sides touching water or the grid boundary.

That is the island perimeter.

## Complexity

Let:

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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(rows * cols)` | We scan every cell once |
| Space | `O(1)` | Only a few variables are used |

## Implementation

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

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    continue

                perimeter += 4

                if r + 1 < rows and grid[r + 1][c] == 1:
                    perimeter -= 2

                if c + 1 < cols and grid[r][c + 1] == 1:
                    perimeter -= 2

        return perimeter
```

## Code Explanation

We first read the grid dimensions:

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

Then we scan each cell:

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

Water cells do not contribute to the perimeter:

```python
if grid[r][c] == 0:
    continue
```

Each land cell begins with four exposed sides:

```python
perimeter += 4
```

If there is land below, the current cell and the lower cell share an edge:

```python
if r + 1 < rows and grid[r + 1][c] == 1:
    perimeter -= 2
```

If there is land to the right, they also share an edge:

```python
if c + 1 < cols and grid[r][c + 1] == 1:
    perimeter -= 2
```

Finally:

```python
return perimeter
```

returns the outside perimeter.

## Alternative DFS View

We can also compute the perimeter by DFS.

From each land cell, explore four directions.

Whenever exploration steps into water or outside the grid, that direction contributes `1` to the perimeter.

This version matches the geometric definition directly.

```python
class Solution:
    def islandPerimeter(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        seen = set()

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

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

            if (r, c) in seen:
                return 0

            seen.add((r, c))

            return (
                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:
                    return dfs(r, c)

        return 0
```

The counting solution is shorter and uses constant extra space, so it is usually the preferred answer.

## Testing

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

    assert s.islandPerimeter([
        [0, 1, 0, 0],
        [1, 1, 1, 0],
        [0, 1, 0, 0],
        [1, 1, 0, 0],
    ]) == 16

    assert s.islandPerimeter([[1]]) == 4
    assert s.islandPerimeter([[1, 0]]) == 4
    assert s.islandPerimeter([[1, 1]]) == 6
    assert s.islandPerimeter([[1], [1]]) == 6

    assert s.islandPerimeter([
        [1, 1],
        [1, 1],
    ]) == 8

    assert s.islandPerimeter([
        [0, 0, 0],
        [0, 1, 0],
        [0, 0, 0],
    ]) == 4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Confirms the expected answer `16` |
| `[[1]]` | Single land cell |
| `[[1,0]]` | One land cell with adjacent water |
| `[[1,1]]` | Horizontal shared edge |
| `[[1],[1]]` | Vertical shared edge |
| `2 x 2` block | Multiple shared edges |
| Center island | Land surrounded by water |