Island Perimeter — Counting Edges Without Traversal (LC 463)

Problem Statement#

LeetCode 463 — Island Perimeter (Easy). You are given a grid where 1 represents land and 0 water. There is exactly one island. Return the perimeter of the island.

Constraints:

• 1 <= m, n <= 100
• grid[i][j] is 0 or 1
• Exactly one island, no lakes inside

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

Why This Problem Matters#

Island Perimeter teaches a powerful interview lesson: not every grid problem needs traversal. Keywords: "Island Perimeter LeetCode 463", "grid counting trick", "no DFS solution", "O(mn) perimeter". Many candidates default to DFS and write 30 lines — the optimal solution is 8 lines and easier to verify. Recognising when traversal is overkill is a senior-level skill.

The Core Insight#

Every land cell contributes 4 edges to the perimeter. Each pair of adjacent land cells shares one edge that is NOT on the perimeter — that pair removes 2 from the total (one edge per cell). So perimeter = 4 * land - 2 * shared_edges.

Visual Dry Run#

For the small example [[1,1],[1,0]] with 3 land cells:

Solution (Optimal)#

class Solution:
    def islandPerimeter(self, grid):
        rows, cols = len(grid), len(grid[0])
        land = 0
        shared = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    land += 1
                    if r + 1 < rows and grid[r + 1][c] == 1:
                        shared += 1
                    if c + 1 < cols and grid[r][c + 1] == 1:
                        shared += 1
        return 4 * land - 2 * shared

var islandPerimeter = function(grid) {
    const rows = grid.length, cols = grid[0].length;
    let land = 0, shared = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 1) {
                land++;
                if (r + 1 < rows && grid[r + 1][c] === 1) shared++;
                if (c + 1 < cols && grid[r][c + 1] === 1) shared++;
            }
        }
    }
    return 4 * land - 2 * shared;
};

Time: O(m * n) — single pass through the grid. Space: O(1) — just two counters.

Common Mistakes#

• Counting shared edges twice by checking all four neighbours instead of only down and right.
• Reaching for DFS when simple counting suffices.
• Forgetting that water adjacent to land contributes to the perimeter implicitly.
• Bounds-checking only inside the inner condition and missing r+1 < rows checks.

Interview Tips#

• Start with the DFS approach to show you can do it, then mention the counting optimisation.
• Explain the formula 4L - 2S clearly on the whiteboard.
• Note that O(1) space is impossible to beat.
• For multi-island variants (LC 695 max area), DFS is necessary.

Follow-up Questions#

• What if there could be multiple islands? Hint: same formula still works.
• What about lakes inside the island? Hint: treat 0 as water unconditionally.
• Largest island after flipping one 0 to 1 (LC 827). Hint: DFS plus map of island sizes.
• Compute perimeter in 8-directional adjacency — diagonals share corners not edges.

Key Takeaways#

• Perimeter = 4 * land_cells - 2 * shared_edges.
• Only check down and right neighbours to avoid double counting.
• DFS solves it but is overkill — pure counting is O(1) space.
• Time complexity is O(m * n) for the single grid scan.
• Recognising when traversal is unnecessary is a senior-level interview skill.
• The shared-edge trick generalises to surface area in 3-D grids (LC 892).
• Always offer the simple solution before the elaborate one.