Island Perimeter

Island Perimeter

1. What is this problem about?

The Island Perimeter interview question gives you a grid representing a map where 1 is land and 0 is water. There is exactly one island. You need to calculate the total perimeter of this island. The perimeter is defined as the number of edges that separate a land cell from a water cell or the boundary of the grid.

2. Why is this asked in interviews?

Companies like Google, Apple, and Bloomberg use this to test basic Matrix interview pattern traversal. It evaluations whether you can correctly identify boundaries and neighbors in a 2D space. While it can be solved with DFS/BFS, there is a much simpler linear scan approach that avoids recursion.

3. Algorithmic pattern used

This problem follows the Neighbor Counting pattern.

1. Iterate: Traverse every cell (r, c) in the grid.
2. Land Check: If grid[r][c] == 1:
   • Assume it contributes 4 to the perimeter.
   • Subtract Redundancy: Check the neighbor to the left and the neighbor above.
   • If the left neighbor is also land, subtract 2 (one from the current cell's perimeter and one from the neighbor's).
   • If the neighbor above is also land, subtract 2.
3. Alternative: Simply iterate through all cells and for every land cell, count how many of its 4 edges are water or the grid boundary.

4. Example explanation

0 1 0
1 1 1
0 1 0

• Cell (0, 1): Land. Perimeter +4.
• Cell (1, 0): Land. Perimeter +4. Total 8.
• Cell (1, 1): Land. Perimeter +4. Total 12.
  • Neighbor left (1, 0) is land. -2. Total 10.
  • Neighbor above (0, 1) is land. -2. Total 8. ... and so on.

5. Common mistakes candidates make

• Over-counting: Forgetting that an edge between two land cells contributes 0 to the perimeter.
• Complexity: Attempting a complex DFS when a nested loop is simpler and handles the single-island constraint just as well.
• Boundary checks: Forgetting to count the edges that touch the outer boundary of the $M \times N$ grid.

6. Interview preparation tip

For grid problems, always ask: "Does the property depend on local neighbors or global connectivity?" Perimeter is local, so a simple scan is usually better than a traversal. This is a great Simulation interview pattern practice.