Island Perimeter - Solution & Explanation

Problem Overview: You receive an m x n binary grid where 1 represents land and 0 represents water. The grid contains exactly one island (connected horizontally or vertically). The task is to calculate the total perimeter of that island by counting the edges where land touches water or the grid boundary.

Approach 1: Iterative Grid Enumeration (O(m*n) time, O(1) space)

Scan every cell in the grid. Each land cell contributes up to four edges to the perimeter. For every grid[i][j] == 1, start with +4 edges, then subtract edges shared with neighboring land cells. Checking the top and left neighbors avoids double counting shared edges. The key insight: every adjacent land pair removes two perimeter edges. This approach relies on simple iteration across the array representing the grid and constant-time neighbor checks.

Approach 2: Depth-First Search (DFS) (O(m*n) time, O(m*n) space)

Start a DFS from the first land cell and explore the entire island using recursion. Whenever the DFS reaches water or goes out of bounds, that edge contributes +1 to the perimeter. If a land cell is already visited, return 0 because its edges were counted earlier. This approach treats the island as a connected component in a matrix and traverses it using depth-first search. It is conceptually clean because each recursive step directly models an edge check around the island boundary.

Recommended for interviews: Iterative grid enumeration is the expected solution. It runs in O(m*n) time with O(1) space and requires only simple neighbor checks. DFS also works and demonstrates strong graph traversal knowledge, but interviewers typically prefer the enumeration approach because it avoids recursion overhead and is easier to reason about during implementation.