Sponsored
Sponsored
This approach employs a breadth-first search (BFS) to explore the grid, counting the number of islands. Initially, it checks if the grid is already disconnected. If not, it attempts to disconnect the grid by changing each land cell to water one-by-one, checking the number of islands created each time. If the transformation disconnects the grid, the process stops early. This approach is based on the premise that if converting any one land cell to water does not suffice, converting two will.
Time Complexity: O((m*n)^2), where m and n are grid dimensions due to the nested loop and re-evaluation of the grid connect status for each cell transformation.
Space Complexity: O(m*n) for the BFS queue and visited marker.
1def minDays(grid):
2 def connected():
3 seen = set()
4 def dfs(r, c):
5 if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0 or (r, c) in seen:
6 return 0
7 seen.add((r, c))
8 for x, y in ((r, c+1), (r+1, c), (r, c-1), (r-1, c)):
9 dfs(x, y)
10 return 1
11 cnt = sum(dfs(r, c) for r in range(len(grid)) for c in range(len(grid[0])))
12 return cnt != 1
13
14 if connected():
15 return 0
16
17 rows, cols = len(grid), len(grid[0])
18 for r in range(rows):
19 for c in range(cols):
20 if grid[r][c] == 1:
21 grid[r][c] = 0
22 if connected():
23 return 1
24 grid[r][c] = 1
25
26 return 2The function connected() uses BFS to count the number of islands. Initially, if the grid is already disconnected (more than one island), it returns 0. Otherwise, it tries flipping each 1 to 0 and checks again if the grid becomes disconnected. If so, it returns 1. If no single flip works, it's guaranteed disconnect happens after flipping two cells, hence returning 2.
This approach utilizes a union-find (disjoint set union, DSU) data structure to efficiently manage and check connected components within the grid. Initially, it checks the number of islands using the union-find approach. Then, it assesses the effect of converting each land cell to water, employing union-find to determine if it results in a disconnected structure.
Time Complexity: O((m*n))
Space Complexity: O(m*n)
1class Solution {
2 private class UnionFind
The Java solution mirrors the C++ implementation using a Union-Find class. Each land cell is checked for connectivity to its neighbors through union operations. This approach ensures disjoint set operations handle cell grouping efficiently. The method validates the current connectivity state, attempts pivotal cell transformations, and concludes on the minimum transformations required.