463. Island Perimeter - Detailed Explanation

Problem Statement

You are given a 2D grid of integers where 0 represents water and 1 represents land. The grid contains exactly one island (i.e. a group of connected 1's connected horizontally or vertically) and there are no lakes (water inside that island that isn’t connected to the water around the island). Your task is to calculate the perimeter of the island.

Examples

Example 1

Input:

grid = [
  [0,1,0,0],
  [1,1,1,0],
  [0,1,0,0],
  [1,1,0,0]
]

Output:

16

Explanation:
The island in the grid has a perimeter of 16.

Example 2

Input:

grid = [
  [1]
]

Output:

4

Explanation:
A single land cell has 4 sides, so the perimeter is 4.

Hints

• Every land cell has 4 sides by itself.

• When two land cells are adjacent (horizontally or vertically), they share a border. Each shared border reduces the total perimeter by 2.

• You can calculate the perimeter by summing 4 for each land cell and subtracting 2 for every pair of adjacent land cells.

• Alternatively, for each land cell, check its four neighbors (top, bottom, left, and right). For each side that is either at the boundary of the grid or adjacent to water, add 1 to the perimeter.

Approach

Method 1: Count Land Cells and Shared Borders

1. Traverse the grid: Iterate through each cell in the grid.
2. Count Land Cells: For every cell that is 1 (land), add 4 to the perimeter count.
3. Subtract Shared Edges: For each land cell, check the right neighbor and the bottom neighbor. If the neighbor is also land, subtract 2 from the total perimeter (one subtraction for each shared edge; since each edge is counted twice when considering both cells, subtracting 2 accounts for both sides).
4. Return the Result: The resulting value is the perimeter of the island.

Method 2: Check All Four Sides for Each Cell

1. Traverse the grid: Iterate through each cell.
2. For each land cell:
   • Check the top, bottom, left, and right neighbors.
   • For each neighbor that is either water or out of the grid bounds, add 1 to the perimeter.
3. Return the Total Perimeter.

Both methods run in O(m*n) time, where m is the number of rows and n is the number of columns in the grid, and use O(1) extra space.

Step-by-Step Walkthrough (Method 2)

1. Initialization:
   Set a variable perimeter to 0.

2. Loop through each cell in the grid:
   For every cell (i, j):

   • If the cell is land (grid[i][j] == 1), check its four sides:

     • Top: If i == 0 (first row) or the cell above is water, add 1.

     • Bottom: If i is at the last row or the cell below is water, add 1.

     • Left: If j == 0 (first column) or the cell to the left is water, add 1.

     • Right: If j is at the last column or the cell to the right is water, add 1.

3. Result:
   After the loop, the perimeter variable holds the total perimeter of the island.

Python Code