My efficient O(mn) solution (87.76%)


  • 0
    M

    This is my solution, which always count each grid edge once and only once.
    Compared to my original "for each land square search for sea or boundary" algorithm (23.8%), this avoids double counting of grid lines in inland area.

    class Solution(object):
        def islandPerimeter(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            ans=0
            h=len(grid)
            w=len(grid[0])
            for i in range(h):
                for j in range(w):
                    if grid[i][j]:
                        ans+=(i==0 or not grid[i-1][j])+(j==0 or not grid[i][j-1])
                    else:
                        ans+=(i!=0 and grid[i-1][j])+(j!=0 and grid[i][j-1])
            for i in range(h):
                ans+=grid[i][w-1]
            for i in range(w):
                ans+=grid[h-1][i]
            return ans
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.