Solution to LeetCode 200 Number of Islands & LeetCode 463 Island Perimeter. Other problems related to ‘island’ are LC 695 and LC 829.
LeetCode 200
Number of Islands (Medium). [link]
1] DFS. Count the number of island and use function DFS to turn all ‘1’ in one island into ‘0’. Time complexity O(height*width), space complexity O(height*width).
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def DFS(grid, w, h):
if w < 0 or h < 0 or h >= height or w >= width or grid[h][w] == '0':
return
grid[h][w] = '0'
DFS(grid, w+1, h)
DFS(grid, w-1, h)
DFS(grid, w, h+1)
DFS(grid, w, h-1)
height = len(grid)
width = len(grid[0])
if height == 0 : return 0
ans = 0
for h in range(height):
for w in range(width):
if grid[h][w] == '1':
ans += 1
DFS(grid, w, h)
return ans
2] BFS. Time complexity O(width*height). Space complexity O(width*height).
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def BFS(grid, w, h):
que = [[w, h]]
while que:
[w,h] = que.pop(0)
if 0 <= h < len(grid) and 0 <= w < len(grid[0]) and grid[h][w] == '1':
grid[h][w] = '0'
que += [[w, h-1],[w,h+1],[w-1,h],[w+1,h]]
height = len(grid)
width = len(grid[0])
if height == 0 : return 0
ans = 0
for h in range(height):
for w in range(width):
if grid[h][w] == '1':
ans += 1
BFS(grid, w, h)
return ans
LeetCode 463
Island Perimeter (Easy). [link]
The perimeter of a land is 4. If it has a neighbor land, the perimeter of the two lands is 4 *2 - 2. So the formula is “4* lands - 2*boundary”.
class Solution(object):
def islandPerimeter(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
width = len(grid[0])
height = len(grid)
if height == 0 and width == 0:
return 0
area = 0
bound = 0
for h in range(height):
for w in range(width):
if grid[h][w] == 1:
area += 1
if h > 0 and grid[h-1][w] == 1:
bound += 1
# if h < height -1 and grid[h+1][w] == 1:
# neighbor += 1
if w > 0 and grid[h][w-1] == 1:
bound += 1
# if w < width -1 and grid[h][w+1] == 1:
# neighbor += 1
return area*4 - bound*2
Approach it in another way, the perimeter of one land is 4, if it has a neighbor, the perimeter decreases by 1. The formula is “4* lands - neighbors”.
class Solution(object):
def islandPerimeter(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
width = len(grid[0])
height = len(grid)
if height == 0 and width == 0:
return 0
area = 0
neighbor = 0
for h in range(height):
for w in range(width):
if grid[h][w] == 1:
area += 1
if h > 0 and grid[h-1][w] == 1:
neighbor += 1
if h < height -1 and grid[h+1][w] == 1:
neighbor += 1
if w > 0 and grid[h][w-1] == 1:
neighbor += 1
if w < width -1 and grid[h][w+1] == 1:
neighbor += 1
return area*4 - neighbor
