💬 Discord
Sign In
NeetCode #556LC-463EasyGraphsNC 250
← Back to All Problems

#556 · #463 · Island Perimeter(岛屿的周长)

📌 Problem Statement & Constraints

You are given a row x col grid of 1s (land) and 0s (water) representing a single island with no lakes. Return the island's perimeter. Constraints: 1 <= row, col <= 100.

💡 Core Algorithmic Approaches

  1. Each land cell contributes 4 to the perimeter, minus 2 for every shared edge with another land cell.
  2. So a single pass counting 4 * land - 2 * shared_edges suffices.
  3. Only the right and down neighbours need checking to count each shared edge once.
  4. A flood-fill counting boundary edges is an equivalent alternative.

💻 Benchmark Python3 Implementation

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        perimeter = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] != 1:
                    continue
                perimeter += 4         # start with all four sides exposed
                # subtract 2 for each shared edge (counted once via right/down)
                if i + 1 < m and grid[i + 1][j] == 1:
                    perimeter -= 2
                if j + 1 < n and grid[i][j + 1] == 1:
                    perimeter -= 2
        return perimeter

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): one pass over the grid.
💾 Space Complexity
O(1): a single accumulator.

⚠️ Interview Pitfalls & Follow-ups

  • Subtracting 2 for all four neighbours: each shared edge would be counted twice.
  • Checking only the right neighbour: the down neighbour also matters.
  • Trying to flood-fill and count boundary edges: workable but more code than the arithmetic identity.
  • Assuming the island has lakes: the constraints exclude them, which is what makes the formula exact.