Solution Analysis and Python Code


  • 0
    T

    Solution Analysis

    The key point here is to identify the land (value == 1) and its adjacent lands. Each land itself has 4 edges, but with adjacent lands, the shared edge is double counted, which should be subtracted from the total perimeter calculation.

    For example, land (0,1) and land (1,1) are adjacent, so the edge between them should be subtracted. When we count, we can count the total edges of each land then do the subtraction:

    1*4 + 1*4 - 2 = 6
    

    Pseudo code:

    # Traverse the two-d array and identify land points.
    row = len(grid)
    col = len(grid[0])
    perimeter = 0
    
    for r in range(row):
        for c in range(col):
            # If this is a land
            if grid[x][y] == 1:
                perimeter += 4
                if grid[x-1][y] == 1:
                    perimeter -=2
                if grid[x][y-1] == 1:
                    perimeter -=2
    return perimeter
    

    Python code:

    def island_perimeter(grid):
        # The total number of rows and cols
        rows = len(grid)
        cols = len(grid[0])
        # Define the perimeter
        p = 0
        for i in range(rows):
            for j in range(cols):
                # This is a land
                if grid[i][j] == 1:
                    p += 4
                    if grid[i-1][j] == 1 and i > 0:
                        p -= 2
                    if grid[i][j-1] == 1 and j > 0:
                        p -= 2
        return p
    

    Complexity analysis

    • Time complexity: O(n^2), n is the row length of the array
    • Space complexity: O(n^2), n is the row length of the array

Log in to reply
 

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