# 463. Island Perimeter

LeetCode Problem Link (opens new window)

Given a row x col 2D grid map grid, where: grid[i][j] = 1 represents land, and grid[i][j] = 0 represents water.

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

There is no "lake" in the island (a "lake" is water within the island that is not connected to the water around the island). Each square is a side length of 1. The grid is rectangular, and both width and height do not exceed 100. Calculate the perimeter of this island.

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: Its perimeter is the 16 yellow edges in the image above.

Example 2:

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

Example 3:

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

Hints:

row == grid.length
col == grid[i].length
1 <= row, col <= 100
grid[i][j] is 0 or 1

# Thought Process

The island problem can easily lead one to think of BFS or DFS, but it is really not necessary for this problem. Don't overcomplicate simple matters.

# Solution One:

Iterate over each cell, and when encountering an island, evaluate its up, down, left, and right. Whenever the surrounding is water or out of bounds, add to the perimeter.

As shown in the diagram:

C++ code as follows: (with detailed comments)

class Solution {
public:
    int direction[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    int islandPerimeter(vector<vector<int>>& grid) {
        int result = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {       // four directions: up, down, left, right
                        int x = i + direction[k][0];
                        int y = j + direction[k][1];    // calculate surrounding coordinates x, y
                        if (x < 0                       // i is on the boundary
                                || x >= grid.size()     // i is on the boundary
                                || y < 0                // j is on the boundary
                                || y >= grid[0].size()  // j is on the boundary
                                || grid[x][y] == 0) {   // x, y position is water
                            result++;
                        }
                    }
                }
            }
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Solution Two:

Calculate the total number of island cells because each pair of adjacent lands decreases the total perimeter count by 2. Then calculate the number of adjacent island pairs.

result = number of island cells * 4 - cover * 2;

As shown in the diagram:

C++ code as follows: (with detailed comments)

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int sum = 0;    // number of land cells
        int cover = 0;  // number of adjacent pairs
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    sum++;
                    // count adjacent land above
                    if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++;
                    // count adjacent land on the left
                    if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++;
                    // Why not count below and right? To avoid double-counting.
                }
            }
        }
        return sum * 4 - cover * 2;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Other Language Versions

# Java:

// Solution One
class Solution {
    // 4 directions: up, down, left, right
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, -1, 1};

    public int islandPerimeter(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0; // island perimeter
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {
                        int x = i + dirx[k];
                        int y = j + diry[k];
                        // The current position is land, and if expanding in four directions results in a "new position" that is "water" or out of bounds, it will contribute an edge to the perimeter
                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
                            res++;
                            continue;
                        }
                    }
                }
            }
        }
        return res;
    }
}

// Solution Two
class Solution {
    public int islandPerimeter(int[][] grid) {
        // Calculate the perimeter of the island 
        // Method two: reduce the total perimeter by 2 for each pair of adjacent lands
        int landSum = 0; // land count 
        int cover = 0; // adjacent land pairs count
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    landSum++;
                    // count adjacent land above
                    if(i - 1 >= 0 && grid[i-1][j] == 1) cover++;
                    // count adjacent land on the left
                    if(j - 1 >= 0 && grid[i][j-1] == 1) cover++;
                }
            }
        }
        return landSum * 4 - cover * 2;
    }
}
// Extension - Traditional DFS solution (using visited array) (increment edge if boundary or water is reached)
class Solution {
    int dir[][] ={
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0}
    };

    boolean visited[][];
    int res = 0;

    public int islandPerimeter(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        visited = new boolean[row][col];

        int result = 0;
        
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(visited[i][j] == false && grid[i][j] == 1)
                    result += dfs(grid, i, j);
            }
        }
        return result;
    }

    private int dfs(int[][] grid, int x, int y){
        // If boundary (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) or water is encountered (grid[x][y] == 0), return 1 (edge + 1)
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0)
            return 1;
        // If this land has already been visited, return 0 to avoid double-counting
        if(visited[x][y])
            return 0;
        int temp = 0;
        visited[x][y] = true;
        for(int i = 0; i < 4; i++){
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            // Store edge in temp
            temp +=dfs(grid, nextX, nextY);
        }
        return temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

# Python:

Iterate over each cell, if the current position is an island grid[i][j] == 1, from this position, evaluate four directions, if the boundary or water is present, add to res matrix for the corresponding cell.

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:

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

        # Create a res 2D array to record the answer
        res = [[0] * n for j in range(m)]

        for i in range(m):
            for j in range(len(grid[i])):
                # If the current position is water, do not modify or reset res[i][j] = 0
                if grid[i][j] == 0:
                    res[i][j] = 0
                # If the current position is land, evaluate in four directions and update res[i][j]
                elif grid[i][j] == 1:
                    if i == 0 or (i > 0 and grid[i-1][j] == 0):
                        res[i][j] += 1
                    if j == 0 or (j >0 and grid[i][j-1] == 0):
                        res[i][j] += 1
                    if i == m-1 or (i < m-1 and grid[i+1][j] == 0):
                        res[i][j] += 1
                    if j == n-1 or (j < n-1 and grid[i][j+1] == 0):
                        res[i][j] += 1

        # Finally, sum up the res matrix. It's not necessarily required to use a matrix to record; using a variable res to record the perimeter could also work, it's just more illustrative with a matrix.
        ans = sum([sum(row) for row in res])

        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# Go:

func islandPerimeter(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    res := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                res += 4
                // four directions: up, down, left, right
                if i > 0 && grid[i-1][j] == 1 {res--} // there's island land above
                if i < m-1 && grid[i+1][j] == 1 {res--} // there's island land below
                if j > 0 && grid[i][j-1] == 1 {res--} // there's island land to the left
                if j < n-1 && grid[i][j+1] == 1 {res--} // there's island land to the right
            }
        }
    }
    return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# JavaScript:

// Solution One
var islandPerimeter = function(grid) {
    // 4 directions: up, down, left, right
    const dirx = [-1, 1, 0, 0], diry = [0, 0, -1, 1];
    const m = grid.length, n = grid[0].length;
    let res = 0; // island perimeter
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] === 1){
                for(let k = 0; k < 4; k++){ // four directions: up, down, left, right
                    // calculate x, y for surrounding coordinates
                    let x = i + dirx[k];
                    let y = j + diry[k];
                    // If the new position expanded in four directions is water or out of bounds, contribute an edge to the perimeter
                    if(x < 0  // i is on the boundary
                    || x >= m // i is on the boundary
                    || y < 0  // j is on the boundary
                    || y >= n // j is on the boundary
                    || grid[x][y] === 0){ // (x,y) position is water
                        res++;
                        continue;
                    }
                }
            }
        }
    }
    return res;
};

// Solution Two
var islandPerimeter = function(grid) {
    let sum = 0; // number of land cells
    let cover = 0; // number of adjacent pairs 
    for(let i = 0; i < grid.length; i++){
        for(let j = 0; j <grid[0].length; j++){
            if(grid[i][j] === 1){
                sum++;
                // count adjacent land above 
                if(i - 1 >= 0 && grid[i-1][j] === 1) cover++;
                // count adjacent land on the left
                if(j - 1 >= 0 && grid[i][j-1] === 1) cover++;
                // Why not count below and right? To avoid double-counting
            }
        }
    }
    return sum * 4 - cover * 2;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

TypeScript:

/**
 * Method 1: Depth First Search (DFS)
 * @param grid Two-dimensional grid where `grid[i][j] = 1` indicates land, and `grid[i][j] = 0` indicates water
 * @returns The perimeter of the island
 */
function islandPerimeter(grid: number[][]): number {
  // Handle special cases: if the grid is empty or has zero rows or columns, return 0 directly
  if (!grid || grid.length === 0 || grid[0].length === 0) {
    return 0;
  }

  // Get the number of rows and columns in the grid
  const rows = grid.length;
  const cols = grid[0].length;
  let perimeter = 0; // Perimeter of the island

  /**
   * Depth First Search function
   * @param i Current cell's row index
   * @param j Current cell's column index
   */
  const dfs = (i: number, j: number) => {
    // If the current position is out of bounds or is water (`grid[i][j] === 0`), increase the perimeter by 1
    if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] === 0) {
      perimeter++;
      return;
    }

    // If the current position has already been visited (`grid[i][j] === -1`), return immediately
    if (grid[i][j] === -1) {
      return;
    }

    // Mark the current position as visited (-1) to avoid double-counting
    grid[i][j] = -1;

    // Continue searching in the four directions: up, down, left, right
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
  };

  // Traverse the entire grid to find the first land cell (`grid[i][j] === 1`), use it as the starting point for DFS
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        dfs(i, j);
        break;
      }
    }
  }

  return perimeter;
}

/**
 * Method 2: Traverse each land cell to calculate the perimeter
 * @param grid Two-dimensional grid where `grid[i][j] = 1` indicates land, and `grid[i][j] = 0` indicates water
 * @returns The perimeter of the island
 */
function islandPerimeter(grid: number[][]): number {
  // Handle special cases: if the grid is empty or has zero rows or columns, return 0 directly
  if (!grid || grid.length === 0 || grid[0].length === 0) {
    return 0;
  }

  // Get the number of rows and columns in the grid
  const rows = grid.length;
  const cols = grid[0].length;
  let perimeter = 0; // Perimeter of the island

  // Traverse the entire grid
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      // If the current cell is land (`grid[i][j] === 1`)
      if (grid[i][j] === 1) {
        perimeter += 4; // Add 4 edges to the perimeter initially

        // Check if the current cell has adjacent land above, if so, subtract 2 edges from the perimeter
        if (i > 0 && grid[i - 1][j] === 1) {
          perimeter -= 2;
        }

        // Check if the current cell has adjacent land on the left, if so, subtract 2 edges from the perimeter
        if (j > 0 && grid[i][j - 1] === 1) {
          perimeter -= 2;
        }
      }
    }
  }

  return perimeter;
}