Island Perimeter

LeetCode 463 | Difficulty: Easy

Easy

Problem Description

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

Example 2:

Input: grid = [[1]]
Output: 4

Example 3:

Input: grid = [[1,0]]
Output: 4

Constraints:

- `row == grid.length`

- `col == grid[i].length`

- `1 <= row, col <= 100`

- `grid[i][j]` is `0` or `1`.

- There is exactly one island in `grid`.

Topics: Array, Depth-First Search, Breadth-First Search, Matrix

---

Approach

BFS (Graph/Matrix)

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 200 ms)

Metric	Value
Runtime	200 ms
Memory	30.3 MB
Date	2020-11-01

Solution

public class Solution {
    public int IslandPerimeter(int[][] grid) {
        int m = grid.Length;
    int n = grid[0].Length;

    int len = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 1)
            {
                int left = i > 0 ? grid[i - 1][j] : 0;
                int right = i < m - 1 ? grid[i + 1][j] : 0;
                int up = j > 0 ? grid[i][j - 1] : 0;
                int down = j < n - 1 ? grid[i][j + 1] : 0;
                if (left == 1 && right == 1 && up == 1 && down == 1)
                    continue;

                len += (left == 0 ? 1 : 0) +
                (right == 0 ? 1 : 0) +
                (up == 0 ? 1 : 0) +
                (down == 0 ? 1 : 0);
            }
        }
    }

    return len;
    }
}

---

Complexity Analysis

Approach	Time	Space
Graph BFS/DFS	$O(V + E)$	$O(V)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.