https://leetcode.com/problems/island-perimeter

How we can evaluate perimeter of our island? We can evaluate perimeters off all squares first, and then subtract all sides of cells, which need to be removed, and that is all!

  1. Perimeter of each cell is equal to 4, so when we see non-empty cell, we add 4.
  2. For each non-empty cell with coordinates (i,j), if (i-1,j) also non-empty, we need to subract 1 from our perimeter, which can be done with line Perimeter -= grid[i][j]*grid[i-1][j]. Note, that for the case 1 1, we subtract 1 twice, so perimeter will be 4+4-1-1 = 6, as it should be. Similar for other neibours of cell (i,j).

image

Complexity: time complexity is O(mn), because we traverse our grid once and for each cell check 4 neighbors. Space complexity is O(1), because we do not use any extraspace, only Perimeter.

class Solution:
    def islandPerimeter(self, grid):
        m, n, Perimeter = len(grid), len(grid[0]), 0

        for i in range(m):
            for j in range(n):
                Perimeter += 4*grid[i][j]
                if i > 0:   Perimeter -= grid[i][j]*grid[i-1][j]
                if i < m-1: Perimeter -= grid[i][j]*grid[i+1][j]
                if j > 0:   Perimeter -= grid[i][j]*grid[i][j-1]
                if j < n-1: Perimeter -= grid[i][j]*grid[i][j+1]
                    
        return Perimeter

If you like the solution, you can upvote it on leetcode discussion section: Problem 0463