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
# Traverse the two-d array and identify land points. row = len(grid) col = len(grid) 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
def island_perimeter(grid): # The total number of rows and cols rows = len(grid) cols = len(grid) # 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
- 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