Problem Description

You have a 2D grid that represents a map. Each cell in the grid contains either:

• 1 representing land
• 0 representing water

The grid forms an island with these characteristics:

• There is exactly one island (a group of connected land cells)
• Land cells connect only horizontally or vertically (not diagonally)
• The entire grid is surrounded by water
• The island has no "lakes" (no water cells completely enclosed within the island)

Your task is to calculate the total perimeter of this island.

The perimeter is the total number of edges where land meets water. Each cell is a square with side length 1, so each exposed edge contributes 1 to the perimeter.

For example, a single land cell 1 surrounded by water would have a perimeter of 4 (all four sides exposed). When land cells are adjacent, they share edges, reducing the total perimeter.

Constraints:

• Grid dimensions don't exceed 100x100
• The grid is rectangular
• There is exactly one island in the grid

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The grid can be viewed as a graph where each cell is a node, and adjacent cells (horizontally/vertically) form edges. We need to explore connected land cells.

Is it a tree?

• No: The grid structure is not a tree. It's a 2D grid where cells can have multiple connections and there's no hierarchical parent-child relationship.

Is the problem related to directed acyclic graphs?

• No: The grid connections are undirected (you can move between adjacent cells in both directions), and it's not about directed relationships.

Is the problem related to shortest paths?

• No: We're not finding the shortest path between points. We're calculating the perimeter of the island.

Does the problem involve connectivity?

• Yes: The problem involves exploring connected land cells to determine the island's boundaries and calculate its perimeter.

Does the problem have small constraints?

• Yes: The grid dimensions don't exceed 100x100, which is relatively small and allows for exhaustive exploration.

DFS/backtracking?

• Yes: DFS is suitable for exploring all connected land cells and marking boundaries where land meets water.

Conclusion: The flowchart suggests using DFS (Depth-First Search) to explore the connected land cells and identify the perimeter. DFS can traverse through all land cells, and for each land cell, we can check its adjacent cells to determine how many edges contribute to the perimeter.

Intuition

The key insight is that each land cell starts with 4 potential edges that could contribute to the perimeter. However, when a land cell shares an edge with another land cell, that shared edge doesn't count toward the perimeter - it's internal to the island.

Think of it this way: imagine placing a single 1x1 square on a table. It has 4 exposed edges, contributing 4 to the perimeter. Now place another square next to it. Each square still has 4 edges, but where they touch, those 2 edges (one from each square) are no longer part of the perimeter - they're internal boundaries.

This leads to a simple counting strategy:

1. For each land cell we find, add 4 to our perimeter count (assuming all edges are exposed)
2. Then check if this land cell has any adjacent land cells
3. For each adjacent land cell, we subtract the shared edges from our count

The clever part is recognizing that when two land cells share an edge, we need to subtract 2 from our total - one edge from each cell that's no longer exposed. To avoid double-counting these subtractions, we only check in two directions (right and down) rather than all four directions. This way, each shared edge is counted exactly once.

For example, if we have two adjacent land cells:

• Cell A contributes +4 to perimeter
• Cell B contributes +4 to perimeter
• They share an edge, so we subtract 2 (one from each)
• Total contribution: 4 + 4 - 2 = 6

This approach eliminates the need for complex DFS traversal or visited tracking - we simply iterate through the grid once, counting and adjusting as we go.

Solution Approach

The implementation uses a simple grid traversal with a counting strategy:

1. Initialize the Grid Dimensions and Counter

m, n = len(grid), len(grid[0])
ans = 0

We store the grid dimensions and initialize our perimeter counter to 0.

2. Traverse Each Cell in the Grid

for i in range(m):
    for j in range(n):

We iterate through every cell in the grid using nested loops.

3. Check if Current Cell is Land

if grid[i][j] == 1:
    ans += 4

When we find a land cell (1), we initially assume all 4 of its edges contribute to the perimeter, so we add 4 to our counter.

4. Check for Adjacent Land Cells (Right)

if i < m - 1 and grid[i + 1][j] == 1:
    ans -= 2

If there's a land cell directly below the current cell (checking bounds first with i < m - 1), these two cells share an edge. We subtract 2 from our counter because:

• The current cell's bottom edge is not part of the perimeter
• The cell below's top edge is not part of the perimeter

5. Check for Adjacent Land Cells (Down)

if j < n - 1 and grid[i][j + 1] == 1:
    ans -= 2

Similarly, if there's a land cell to the right (checking bounds with j < n - 1), we subtract 2 for the shared vertical edge.

Why Only Check Right and Down? By only checking in two directions instead of all four, we ensure each shared edge is counted exactly once. When we're at cell (i,j) and check cell (i+1,j), we handle that shared edge. Later, when we reach cell (i+1,j), we don't need to check upward because we've already accounted for that shared edge.

Time Complexity: O(m × n) where m and n are the grid dimensions, as we visit each cell once.

Space Complexity: O(1) as we only use a constant amount of extra space for variables.

Example Walkthrough

Let's trace through a small example to illustrate the solution approach:

Grid:
[
  [0, 1, 0],
  [1, 1, 1],
  [0, 1, 0]
]

This forms a plus-shaped island. Let's calculate its perimeter step by step:

Initial state: ans = 0

Row 0, Column 0: grid[0][0] = 0 (water) → skip

Row 0, Column 1: grid[0][1] = 1 (land)

• Add 4 to perimeter: ans = 0 + 4 = 4
• Check right (0,2): water → no adjustment
• Check down (1,1): land → subtract 2: ans = 4 - 2 = 2

Row 0, Column 2: grid[0][2] = 0 (water) → skip

Row 1, Column 0: grid[1][0] = 1 (land)

• Add 4 to perimeter: ans = 2 + 4 = 6
• Check right (1,1): land → subtract 2: ans = 6 - 2 = 4
• Check down (2,0): water → no adjustment

Row 1, Column 1: grid[1][1] = 1 (land)

• Add 4 to perimeter: ans = 4 + 4 = 8
• Check right (1,2): land → subtract 2: ans = 8 - 2 = 6
• Check down (2,1): land → subtract 2: ans = 6 - 2 = 4

Row 1, Column 2: grid[1][2] = 1 (land)

• Add 4 to perimeter: ans = 4 + 4 = 8
• Check right: out of bounds → no adjustment
• Check down (2,2): water → no adjustment

Row 2, Column 0: grid[2][0] = 0 (water) → skip

Row 2, Column 1: grid[2][1] = 1 (land)

• Add 4 to perimeter: ans = 8 + 4 = 12
• Check right (2,2): water → no adjustment
• Check down: out of bounds → no adjustment

Row 2, Column 2: grid[2][2] = 0 (water) → skip

Final perimeter: 12

To verify: The plus shape has 5 land cells. Each cell initially contributes 4 edges (5 × 4 = 20). There are 4 shared edges (each removing 2 from the count), so: 20 - (4 × 2) = 12 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid. The algorithm uses nested loops to iterate through every cell in the grid exactly once. For each cell, it performs constant time operations (checking if it's land, adding to perimeter, and checking adjacent cells), resulting in O(1) work per cell. Therefore, the total time complexity is O(m * n).

Space Complexity: O(1). The algorithm only uses a constant amount of extra space for variables (m, n, ans, i, j) regardless of the input size. It modifies the perimeter count in-place without using any additional data structures that scale with the input size.

Common Pitfalls

1. Double-Counting Shared Edges

Pitfall: A common mistake is checking all four directions (up, down, left, right) for each land cell and subtracting 1 for each adjacent land cell found. This leads to double-counting because each shared edge gets processed twice - once from each of the two cells sharing it.

Example of Incorrect Approach:

# INCORRECT - counts each shared edge twice
for i in range(m):
    for j in range(n):
        if grid[i][j] == 1:
            ans += 4
            # Checking all 4 directions
            if i > 0 and grid[i-1][j] == 1:
                ans -= 1  # Up
            if i < m-1 and grid[i+1][j] == 1:
                ans -= 1  # Down
            if j > 0 and grid[i][j-1] == 1:
                ans -= 1  # Left
            if j < n-1 and grid[i][j+1] == 1:
                ans -= 1  # Right

Solution: Only check in two directions (right and down) and subtract 2 for each shared edge found. This ensures each edge is counted exactly once.

2. Incorrect Boundary Checking

Pitfall: Forgetting to check array bounds before accessing neighboring cells, leading to IndexError.

Example of Incorrect Code:

# INCORRECT - may cause IndexError
if grid[i + 1][j] == 1:  # Missing bounds check
    ans -= 2

Solution: Always verify that indices are within bounds before accessing array elements:

if i < m - 1 and grid[i + 1][j] == 1:
    ans -= 2

3. Wrong Subtraction Value

Pitfall: Subtracting only 1 instead of 2 when finding adjacent land cells. Remember that a shared edge affects the perimeter count of both cells sharing it.

Example of Incorrect Logic:

# INCORRECT - only subtracting 1
if i < m - 1 and grid[i + 1][j] == 1:
    ans -= 1  # Should be -2

Solution: Subtract 2 for each shared edge (1 from each cell's contribution).

4. Alternative Correct Approach

Instead of the add-4-then-subtract method, you can count exposed edges directly:

def islandPerimeter(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    perimeter = 0
  
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                # Check all 4 directions
                # Top edge
                if i == 0 or grid[i-1][j] == 0:
                    perimeter += 1
                # Bottom edge
                if i == rows-1 or grid[i+1][j] == 0:
                    perimeter += 1
                # Left edge
                if j == 0 or grid[i][j-1] == 0:
                    perimeter += 1
                # Right edge
                if j == cols-1 or grid[i][j+1] == 0:
                    perimeter += 1
  
    return perimeter

This approach directly counts edges that face water or grid boundaries, avoiding the subtraction logic altogether.