Python detailed solution with explanation


  • 0
    G

    Solution

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

    Count all grids and neighbors: O(MN)

    • For every grid which is 1, the contribution to the perimeter is 4 - x where x is the number of neighbors which are 1 as well.
    class Solution(object):
        def islandPerimeter(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            M, N, perimeter = len(grid), len(grid[0]), 0
            for i in range(M):
                for j in range(N):
                    if grid[i][j] == 1:
                        for x,y in ((i+1,j), (i-1,j), (i,j+1), (i, j-1)):
                            if 0<=x<M and 0<=y<N:
                                perimeter += int(grid[x][y] == 0)
                            else:
                                perimeter += 1
            return perimeter
    

    Count all 1s and adjust for the neighbors: O(MN)

    • When a grid is 1, then add 4 to the perimeter.
    • If the right neighbor is 1, remove 2 from the perimeter count otherwise there will be a double counting issue. Say a and b are right neighbors. Their real contibution to perimeter is 3+3 which can be expressed as 4 - 2 (common boundary) + 4.
    • If the down neighbor is 1, remove 2 from perimeter. Same argument as above.
    class Solution(object):
        def islandPerimeter(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            M, N, perimeter = len(grid), len(grid[0]), 0
            for i in range(M):
                for j in range(N):
                    if grid[i][j] == 1:
                        perimeter += 4
                        for x,y in ((i+1,j), (i,j+1)):
                            if x<M and y<N and grid[x][y]:
                                perimeter -= 2
            return perimeter
    ``

Log in to reply
 

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