O(mn)time O(1)space python solution beats 92%


  • 0
    J

    Idea:

    1. Total edge will +2 if a cell is only connected to a previous one; total edge wont change if a cell is connected to 2 previous ones.
    2. It is not possible for a cell to connect to more than 2 previous cells.
      Therefore, just simple iterate through the array, and check if the current cell is connected to any previous ones, and add up the numbers.
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        solution = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                connected = 0
                if grid[i][j] == 1:
                    if i-1 >= 0:
                        if grid[i-1][j]==1:
                            connected+=1
                    if j-1 >= 0:
                        if grid[i][j-1]==1:
                            connected+=1
                    solution += 4-connected*2
        return solution

Log in to reply
 

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