LeetCode: Island Perimeter

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.

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.

Depth first search(DFS) with count

This is a typical DFS problem, but we need to store the boundary counts during the searching process.

The perimeter contains edges in two categories:

The water cell adjacent to a land cell
The land cell’s edges located at the border of map

For convenient , we set the grid value into 2 if we visited a cell, otherwise we need another extra memory to store the visited information.

Time complexity is O(M*N).

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int row, int col) {
        int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        grid[row][col] = 2;
        for(int i=0; i<4; i++) {
            int nx = row + dir[i][0];
            int ny = col + dir[i][1];
            if(nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size()) {
                if(grid[nx][ny] == 1)
                    dfs(grid, nx, ny);
                else if(grid[nx][ny] == 0) 
                    ans++;
            } else 
                ans++;
        }
    }
    int islandPerimeter(vector<vector<int>>& grid) {
        ans = 0;
        for(int i=0; i<grid.size(); i++) {
            for(int j=0; j<grid[0].size(); j++) {
                if(grid[i][j] == 1) {
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }

    int ans;
};

Bruce-Force

If you think about more, we may find out that we don’t need to use DFS or BFS.

We only need to iterate all the cells and calculate the boundary edges (according to the two above categories).

Time complexity is O(M*N).

class Solution {
public:
    int dirs[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    int islandPerimeter(vector<vector<int>>& grid) {
        int ans = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {  // new island grid cell
                    for (int k = 0; k < 4; k++) {     
                        int x = i + dirs[k][0];
                        int y = j + dirs[k][1];    
                        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()   //category 2
                            || grid[x][y] == 0)  // category 1
                        {   
                            ans++;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

Preparing for an interview? Check out this!

Join my Email List for more insights, It's Free!😋

← Binary Search LeetCode: Defuse the Bomb →