You are given row x col
grid
representing a map where grid[i][j] = 1
represents land and grid[i][j] = 0
represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid
is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
Example 1:
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] Output: 16 Explanation: The perimeter is the 16 yellow stripes in the image above.
Example 2:
Input: grid = [[1]] Output: 4
Example 3:
Input: grid = [[1,0]] Output: 4
Constraints:
row == grid.length
col == grid[i].length
1 <= row, col <= 100
grid[i][j]
is 0
or 1
.Source
def island_perimeter(grid):
"""Naive answer
Time Complexity: O(nm)
Space Complexity: O(1)
"""
def edges(i, j):
nonlocal rows, cols
up = 1 if i > 0 and grid[i-1][j] == 1 else 0 # actually not needed
down = 1 if i < rows-1 and grid[i+1][j] == 1 else 0
left = 1 if j > 0 and grid[i][j-1] == 1 else 0 # actually not needed
right = 1 if j < cols-1 and grid[i][j+1] == 1 else 0
return 4 - up - down - left - right
rows, cols = len(grid), len(grid[0])
perimeter = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
perimeter += edges(r, c)
return perimeter
def island_perimeter(grid):
"""similar as above but with a bit of optimization
Time Complexity: O(nm)
Space Complexity: O(1)
"""
def edges(i, j):
nonlocal rows, cols
down = 2 if i < rows-1 and grid[i+1][j] == 1 else 0 # only those have not been counted
right = 2 if j < cols-1 and grid[i][j+1] == 1 else 0 # by previous iteration of edges(r, c)
return 4 - down - right
rows, cols = len(grid), len(grid[0])
perimeter = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
perimeter += edges(r,c)
return perimeter
def island_perimeter(grid):
"""similar but with Space Complexity: O(nm)"""
rows = len(grid)
cols = len(grid[0])
extended_grid = [[0]*(cols+2)] + [[0]+row+[0] for row in grid] + [[0]*(cols+2)]
perimeter = 0
for i in range(rows+1):
for j in range(cols+1):
if extended_grid[i][j] != extended_grid[i][j+1]:
# land | sea or sea | land
perimeter += 1
if extended_grid[i][j] != extended_grid[i+1][j]:
# sea land
# ------ or ------
# land sea
perimeter += 1
return perimeter
def island_perimeter(grid):
"""by zipping rows together and columns together
[[a, b, c, d], [(a,a,a,a,a),
[a, b, c, d], (b,b,b,b,b),
MAT = [a, b, c, d], --> zip(*MAT) = zip object (c,c,c,c,c),
[a, b, c, d], (d,d,d,d,d)]
[a, b, c, d]]
"""
# convert each row into a string: '0+i[0]i[1]i[2]...i[n]+0' and store it as a list in grid_r
grid_r = ['0' + ''.join(str(r) for r in row) + '0' for row in grid]
# convert each column into a string: '0+j[0]j[1]j[2]...j[n]+0'' and store it as a list in grid_c
grid_c = ['0' + ''.join(str(c) for c in col) + '0' for col in zip(*grid)]
return sum(row.count('01') + row.count('10') for row in grid_r + grid_c)
# grid_r + grid_c means that it will first check grid_r and then grid_c
# '01' | '10'
# ---------------------------------|---------------------------------
# grid_r | grid_c | grid_r | grid_c
# ----------------|----------------|----------------|------------------
# | sea | | land
# sea | land | ------ | land | sea | ------
# | land | | sea
from itertools import chain
def island_perimeter(grid):
"""Variation of the one just above using zip() but with generator instead of list
--> more space efficient.
--> requires chain() to do grid_r + grid_c
"""
grid_r = ('0' + ''.join(str(r) for r in row) + '0' for row in grid)
grid_c = ('0'+''.join(str(c) for c in col) + '0' for col in zip(*grid))
return sum(row.count('01') + row.count('10') for row in chain(grid_r, grid_c))
def island_perimeter(grid):
perimeter = 0
for row in grid + list(map(list, zip(*grid))):
# map(list, zip()) --> convert tuples inside zip into list
# list(zip) --> convert zip object into list
for i, j in zip([0] + row, row + [0]):
if i != j:
perimeter += 1
return perimeter
import operator
def island_perimeter(grid):
"""Same as above but in one line
Note: operator.ne = '!='
'"""
return sum(sum(map(operator.ne, [0] + row, row + [0])) for row in grid + list(map(list, zip(*grid))))
grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
island_perimeter(grid)
16
grid = [[1]]
island_perimeter(grid)
4
grid = [[1,0]]
island_perimeter(grid)
4