Island Perimeter Problem

Problem

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn’t have “lakes”, meaning the water inside isn’t connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine 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 perimeter is the 16 yellow stripes in the image above.

Example 2:

Input:
grid = [ [1] ]
Output:
 4

Example 3:

Input:
grid = [ [1,0] ]
Output:
 4

Solution

Method 1 - Iterative approach counting borders

In this method, we iterate through each cell of the grid. For every cell that represents land (denoted by 1), we initially assume it contributes 4 units to the perimeter. Then, we adjust this count based on the neighboring cells.

  • For each land cell (grid[r][c] == 1), add 4 to the perimeter count since the cell has four potential sides.
  • Check the left neighbor (grid[r][c-1]) and the top neighbor (grid[r-1][c]). If either of these neighbors is also land (1), it means the shared side between the current cell and its neighbor is internal to the island and should not contribute to the perimeter. Therefore, we subtract 2 from the perimeter count for each such shared side.

Code

Java
class Solution {
    public int islandPerimeter(int[][] grid) {
        int ans = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    ans += 4;
                    if (i < m - 1 && grid[i + 1][j] == 1) {
                        ans -= 2;
                    }
                    if (j < n - 1 && grid[i][j + 1] == 1) {
                        ans -= 2;
                    }
                }
            }
        }
        return ans;
    }
}
Python3
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    ans += 4
                    if i < m - 1 and grid[i + 1][j] == 1:
                        ans -= 2
                    if j < n - 1 and grid[i][j + 1] == 1:
                        ans -= 2
        return ans
TypeScript
function islandPerimeter(grid: number[][]): number {
    let m = grid.length,
        n = grid[0].length;
    let ans = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            let top = 0,
                left = 0;
            if (i > 0) {
                top = grid[i - 1][j];
            }
            if (j > 0) {
                left = grid[i][j - 1];
            }
            let cur = grid[i][j];
            if (cur != top) ++ans;
            if (cur != left) ++ans;
        }
    }
    // 最后一行， 最后一列
    for (let i = 0; i < m; ++i) {
        if (grid[i][n - 1] == 1) ++ans;
    }
    for (let j = 0; j < n; ++j) {
        if (grid[m - 1][j] == 1) ++ans;
    }
    return ans;
}
C++
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    ans += 4;
                    if (i < m - 1 && grid[i + 1][j] == 1) ans -= 2;
                    if (j < n - 1 && grid[i][j + 1] == 1) ans -= 2;
                }
            }
        }
        return ans;
    }
};
Go
func islandPerimeter(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				ans += 4
				if i < m-1 && grid[i+1][j] == 1 {
					ans -= 2
				}
				if j < n-1 && grid[i][j+1] == 1 {
					ans -= 2
				}
			}
		}
	}
	return ans
}

Complexity

  • Time: O(n*m)
  • Space: O(1)

Method 2 - DFS

We can start from some point on land, and start the DFS. We can go in any direction(up, down, left and right) from current point, i.e. grid[r][c] where r and c are current row and column.

  • If a cell is out of the grid bounds or is water (0), it contributes 1 to the perimeter (since water cells have an exposed border).
  • If a cell is land (1), we mark it as visited to avoid recounting, then recursively explore its four neighboring cells (up, down, left, right).
  • The base case for the recursion is when the cell is out of bounds or is water, which contributes 1 to the perimeter.

Code

Java
class Solution {
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    boolean[][] visited;
    int perimeter;

    public int islandPerimeter(int[][] grid) {
        visited = new boolean[grid.length][grid[0].length];
        perimeter = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    dfs(i, j, grid);
                    break;
                }
            }
        }

        return perimeter;
    }

    private void dfs(int r, int c, int[][] grid) {
        visited[r][c] = true;
        for (int i = 0; i < 4; i++) {
            int newR = r + dx[i];
            int newC = c + dy[i];
            if (newR < 0 || newC < 0 || newR >= grid.length || newC >= grid[0].length) {
                perimeter++;
            } else if (grid[newR][newC] == 0) {
                perimeter++;
            } else {
                if (!visited[newR][newC]) {
                    dfs(newR, newC, grid);
                }
            }
        }
    }
}

Complexity

  • Time: O(n*m)
  • Space: O(1)