Problem description:

You are given a map in form of a two-dimensional integer grid where 1 represents land and 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” (water inside that 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.

Example:

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

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

Solution:

Count the total number of grid that is 1 from top to down and from left to right.

When we’re counting the perimeter, if there’s any neighbor of a grid, it will cancel off two edges.
ex:

1
2
3
4
+--+     +--+                   +--+--+
|  |  +  |  |          ->       |     |
+--+     +--+                   +--+--+
2 islands

1
4 + 4 - ? = 6  -> ? = 2

While we’re scanning the grid, we need to know how many neighbor does this grid have. Since we’re scanning from top to down, we only need to count the neighbor its row is above the grid.

Same thing about the neighbor that has different column, only need to count neighbor that is on the left side.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        island, neighbor = 0, 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    island += 1
                    if i < len(grid)-1 and grid[i+1][j] == 1: 
                        neighbor += 1 # bottom neighbor
                    if j < len(grid[0])-1 and grid[i][j+1] == 1: 
                        neighbor += 1 # right neighbor
        
        return 4*island -neighbor*2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int neighbor= 0, count= 0;
        for(int r= 0; r< grid.size(); r++){
            for(int c= 0; c< grid[0].size(); c++){
                if(grid[r][c] == 1){
                    //this is 1, search how many neighbor around it.
                    count++;
                    if(r != 0 && grid[r-1][c]== 1) neighbor++;
                    if(c != 0 && grid[r][c-1]== 1) neighbor++;
                }
            }
        }
        
        return count*4-neighbor*2;
    }
};

time complexity: $O(mn)$
space complexity: $O(1)$
reference:
https://goo.gl/5rZHRg