Problem Statement

You are given a 2D grid map where:

• 1 represents land, and
• 0 represents water.

The grid is completely surrounded by water, and there is exactly one island (a group of connected lands).
The island doesn’t have any lakes (water inside the island).

You need to return the perimeter of the island.

Example:

Input:
[
 [0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]
]

Output: 16

---

Approach: Count Land Edges and Subtract Shared Sides

To calculate the perimeter, observe the following:

1. Each land cell contributes 4 sides.
2. However, if two land cells are adjacent (either vertically or horizontally), each shared side should be subtracted once for both cells, meaning subtract 2 for every shared edge.

Thus, the algorithm is:

• Traverse every cell in the grid.
• For each land cell:
  • Add 4 to the perimeter.
  • Subtract 2 for each adjacent land cell (down and right neighbors only to avoid double subtraction).

---

Java Solution

public class Solution {
    public int islandPerimeter(int[][] grid) {
        int perimeter = 0;
        int rows = grid.length;
        int cols = grid[0].length;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    perimeter += 4;
                    
                    // Check the cell above
                    if (i > 0 && grid[i - 1][j] == 1) {
                        perimeter -= 2;
                    }

                    // Check the cell to the left
                    if (j > 0 && grid[i][j - 1] == 1) {
                        perimeter -= 2;
                    }
                }
            }
        }
        return perimeter;
    }
}

---

Complexity Analysis

• Time Complexity: O(m × n), where m and n are the grid dimensions, since each cell is visited once.
• Space Complexity: O(1), as no extra data structures are used.

---

Step-by-Step Explanation

1. Traverse every cell in the grid.
2. For each land cell:
   • Add 4 to the perimeter.
   • If the top cell is also land, subtract 2.
   • If the left cell is also land, subtract 2.
3. Return the total perimeter at the end.

---

Dry Run

Input Grid:

[
 [0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]
]

Step	Cell (i,j)	Is Land?	Action	Perimeter
(0,1)	Yes	+4	4
(1,0)	Yes	+4	8
(1,1)	Yes	+4, shared top → -2, shared left → -2	8
(1,2)	Yes	+4, shared left → -2	10
(2,1)	Yes	+4, shared top → -2	12
(3,0)	Yes	+4	16
(3,1)	Yes	+4, shared top → -2, shared left → -2	16

Final Perimeter = 16

---

Key Insight

The algorithm cleverly avoids double-counting shared edges by checking only top and left neighbors.
If you checked all four directions, you would subtract twice per shared edge, giving the wrong result.