Making A Large Island — LeetCode 827 Python Solution
HardDepth-First SearchBreadth-First SearchUnion FindArrayMatrix
- Problem
- #827
- Pattern
- Union-Find
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Example
- Input
- grid = [[1,0],[0,1]]
- Output
- 3
- Explanation
- Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Python solution
Python
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
def dfs(i: int, j: int):
p[i][j] = root
cnt[root] += 1
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and grid[x][y] and p[x][y] == 0:
dfs(x, y)
n = len(grid)
cnt = Counter()
p = [[0] * n for _ in range(n)]
dirs = (-1, 0, 1, 0, -1)
root = 0
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x and p[i][j] == 0:
root += 1
dfs(i, j)
ans = max(cnt.values() or [0])
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 0:
s = set()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n:
s.add(p[x][y])
ans = max(ans, sum(cnt[root] for root in s) + 1)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n^2) |
| Space | O(n^2) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 827. Making A Large Island is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 827. Making A Large Island?
- LeetCode 827. Making A Large Island is rated Hard on LeetCode.
- What is the time complexity of LeetCode 827. Making A Large Island?
- The Python solution on this page runs in O(n^2).
- What is the space complexity of LeetCode 827. Making A Large Island?
- The Python solution on this page uses O(n^2) auxiliary space.
- What topics does LeetCode 827. Making A Large Island cover?
- LeetCode 827. Making A Large Island is tagged Depth-First Search, Breadth-First Search, Union Find, Array and Matrix on LeetCode.