LeetCode Daily Question 11/08/2024 - 1568. Minimum Number of Days to Disconnect Island
Problem Description:
You are given an m x n binary grid grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally (horizontal or vertical) connected group of 1's. The grid is said to be connected if we have exactly one island, otherwise is said disconnected. In one day, we are allowed to change any single land cell (1) into a water cell (0). Return the minimum number of days to disconnect the grid.
Solution:
class Solution:
directions = [(0,1),(1,0),(-1,0),(0,-1)]
class ArticulationPoints:
def __init__(self, isArticulationPoint, time):
self.isArticulationPoint = isArticulationPoint
self.time = time
def minDays(self, grid:List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
discovery = [[-1] * n for _ in range(m)]
parents = [[-1] * n for _ in range(m)]
lowLinkVal = [[-1] * n for _ in range(m)]
cellCount = 0
islandCount = 0
articulationPoint = self.ArticulationPoint(False, 0)
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
cellCount += 1
if discovery[i][j] == -1:
self.findArticulationPoints(grid, i, j, discovery, lowLinkVal, parents, articulationPoint)
islandCount += 1
if islandCount == 0 or islandCount >= 2:
return 0
if cellCount == 1:
return 1
if articulationPoint.isArticulationPoint:
return 1
return 2
def findArticulationPoints(grid, i, j, discovery, lowLinkVal, parents, articulationPoint):
m = len(grid)
n = len(grid[0])
discovery[i][j] = articulationPoint.time
lowLinkVal[i][j] = discovery[i][j]
children = 0
for dx, dy in self.directions:
newRow = i + dx
newCol = j + dy
if 0 <= newRow < m and 0 <= newCol < n and grid[newRow][newCol] == 1:
if discovery[newRow][newCol] == -1:
children += 1
parents[newRow][newCol] = i * n + j
self.findArticulationPoints(grid, newRow, newCol, discovery, lowLinkVal, parents,
articulationPoint)
lowLinkVal[i][j] = min(lowLinkVal[i][j], lowLinkVal[newRow][newCol])
if (lowLinkVal[newRow][newCol] >= discovery[i][j] and parents[i][j] != -1):
articulationPoint.isArticulationPoint = True
elif newRow * n + newCol != parents[i][j]:
lowLinkVal[i][j] = min(lowLinkVal[i][j], discovery[newRow][newCol])
if children > 1 and parents[i][j] == -1:
articulationPoint.isArticulationPoint = TrueExplanation:
This is a graph problems that can be solved by identifying articulation points.
To simply put, articulation points are weak points of a(n) (un)directed graph. Removing these points will cause the graph to split into disconnected components.
#Consider the following graph
1 -- 2
| |
3 -- 4
\
5
# When vertex '3' is removed, we are left with 2 separated components.
1 -- 2
| 5
4The vertex '3' is an articulation point. If we remove 3 we result in a disconnect graph with 2 components.
Thus, the problem of finding how many land cells to remove to disconnect the island is the same as determining if there are articulation points in our undirected graph.
To determine the articulation points of a graph, we could use Trajan's Algorithm. This algorithm works by traversing the graph as a DFS tree.
We call x the parent if y if we must go through x to find y, or x discovers y.
To be an articulation point, a vertex x must satisfy either :
- x is the root of the DFS tree and has at least 2 children
OR
- x is not the root of the DFS tree and all subtree of x has no connection to parents of x.
1
/ |
2 3
|
4
/ | \
5 6 7
#Vertex '3' is not a root of the DFS tree and the subtree rooted at '4' (its children)
#has no edges connected to parents / ancestors of '3'.
#So removing '3' will result in 4 disconnected components.
1
/ | 5 6 7
2 3
#On the other hand, if we consider the DFS tree:
1
/ | \
2 3 \
| \
4 -- 7
/ |
5 6
#Removing '3' is not going to disconnect the components, so '3' in this case is not an articulation point.Another key concept is the low-link value of a vertex.
The low-link value of a vertex is the smallest discovery time reachable from that vertex, either directly or indirectly.
To make this more concrete, we consider an example.
A - B - C
\ |
D
#When we traverse this tree, we first arrive at 'A' (discovers 'A'), then 'B', then 'C', then 'D'.
#So we would say
discovery lowLinkVal #Assume they are the same as the discovery time of that vertex.
A: 1 A: 1
B: 2 B: 2
C: 3 C: 3
D: 4 D: 4
#The shortest discovery time is determined by the number of back-edges a vertex have.
#These back-edges provide short cuts to discover other vertices.
#Note that low[x] = min(discovery[x], min(low[y] for all adjacent y), min(discovery[y] for back-edges y))
'D' has no back-edges, so lowLinkVal['D'] = discovery['D']
'C' connects directly with 'B' so lowLinkVal['C'] = min(discovery['B'],discovery['C']) = 2
'B' connects with 'A', 'C', and 'D',
so lowLinkVal['B'] = min(discovery['B'], lowLinkVal['C'], lowLinkVal['D']) = 2
#We just check back-edges which are the edges 'B' - 'C' and 'B' - 'D'.
'A' connects with 'B' and indirectly with 'C', 'D' via 'B' so
lowLinkVal['A'] = min(discovery['A'], lowLinkVal['B']) = 1
#Hence,
lowLinkVal
A: 1
B: 2
C: 2
D: 4Putting these together we can begin to construct our solution.
We first define the articulation points class.
class ArticulationPoints:
def __init__(self, isArticulationPoint, time):
self.isArticulationPoint = isArticulationPoint
self.time = timeThen we can set up our helper functions to find articulation points
def findArticulationPoints(self, grid, i, j, discovery, lowLinkVal, parents, articulationPoint):
m = len(grid)
n = len(grid[0])
discovery[i][j] = articulationPoint.time
lowLinkVal[i][j] = discovery[i][j]
children = 0
for dx, dy in self.directions:
newRow = i + dx
newCol = j + dy
if self.isIsland(grid, newRow, newCol):
if discovery[newRow][newCol] == -1:
children += 1
parents[newRow][newCol] = i * n + j
self.findArticulationPoints(grid, newRow, newCol, discovery, lowLinkVal, parents, articulationPoint)
lowLinkVal[i][j] = min(lowLinkVal[i][j], lowLinkVal[newRow][newCol])
if (lowLinkVal[newRow][newCol] >= discovery[i][j] and parents[i][j] != -1):
articulationPoint.isArticulationPoint = True
elif newRow * n + newCol != parents[i][j]:
lowLinkVal[i][j] = min(lowLinkVal[i][j], discovery[newRow][newCol])
if children > 1 and parents[i][j] == -1:
articulationPoint.isArticulationPoint = TrueWe are now ready to solve the problem.
def minDays(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
discovery = [[-1] * n for _ in range(m)]
parents = [[-1] * n for _ in range(m)]
lowLinkVal = [[-1] * n for _ in range(m)]
cellCount = 0
islandCount = 0
articulationPoint = self.ArticulationPoints(False, 0)
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
cellCount += 1
if discovery[i][j] == -1:
self.findArticulationPoints(grid, i, j, discovery, lowLinkVal, parents, articulationPoint)
islandCount += 1
if islandCount == 0 or islandCount >= 2:
return 0
if cellCount == 1:
return 1
if articulationPoint.isArticulationPoint:
return 1
return 2