Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/827.html
827. Making A Large Island (Hard)
In a 2D grid of 0s and 1s, we change at most one 0 to a 1.
After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).
Example 1:
Input: [[1, 0], [0, 1]] Output: 3 Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:
Input: [[1, 1], [1, 0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:
Input: [[1, 1], [1, 1]] Output: 4 Explanation: Can't change any 0 to 1, only one island with area = 4.
Notes:
1 <= grid.length = grid[0].length <= 50.0 <= grid[i][j] <= 1.
Related Topics: Depth-first Search
Solution 1. Union Find
// OJ: https://leetcode.com/problems/making-a-large-island/
// Time: O(MN)
// Space: O(MN)
class UnionFind {
vector<int> id, size;
public:
UnionFind(int N) : id(N), size(N, 1) {
iota(begin(id), end(id), 0);
}
int find(int x) {
return id[x] == x ? x : (id[x] = find(id[x]));
}
void connect(int x, int y) {
int p = find(x), q = find(y);
if (p == q) return;
id[p] = q;
size[q] += size[p];
}
int getSize(int x) { return size[find(x)]; }
};
class Solution {
public:
int largestIsland(vector<vector<int>>& G) {
int M = G.size(), N = G[0].size(), dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, ans = 0;
UnionFind uf(M * N);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (G[i][j] == 0) continue;
for (auto &[dx, dy] : dirs) {
int x = i + dx, y = j + dy;
if (x < 0 || y < 0 || x >= M || y >= N || G[x][y] == 0) continue;
uf.connect(i * N + j, x * N + y);
}
ans = max(ans, uf.getSize(i * N + j));
}
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (G[i][j] == 1) continue;
unordered_map<int, int> m;
for (auto &[dx, dy] : dirs) {
int x = i + dx, y = j + dy;
if (x < 0 || y < 0 || x >= M || y >= N || G[x][y] == 0) continue;
m[uf.find(x * N + y)] = uf.getSize(x * N + y);
}
int size = 1;
for (auto &p : m) size += p.second;
ans = max(ans, size);
}
}
return ans;
}
};
-
class Solution { int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; public int largestIsland(int[][] grid) { int side = grid.length; int[][] islandNumbers = new int[side][side]; int islandCount = 0; int maxSize = 0; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); List<int[]> zeros = new ArrayList<int[]>(); for (int i = 0; i < side; i++) { for (int j = 0; j < side; j++) { if (grid[i][j] == 0) zeros.add(new int[]{i, j}); else if (islandNumbers[i][j] == 0) { islandCount++; int size = breadthFirstSearch(grid, islandNumbers, islandCount, i, j); maxSize = Math.max(maxSize, size); map.put(islandCount, size); } } } for (int[] zero : zeros) { int size = 1; Set<Integer> islandsSet = new HashSet<Integer>(); int row = zero[0], column = zero[1]; for (int[] direction : directions) { int newRow = row + direction[0], newColumn = column + direction[1]; if (newRow >= 0 && newRow < side && newColumn >= 0 && newColumn < side) { int islandNumber = islandNumbers[newRow][newColumn]; if (islandNumber > 0) islandsSet.add(islandNumber); } } for (int island : islandsSet) size += map.get(island); maxSize = Math.max(maxSize, size); } return maxSize; } public int breadthFirstSearch(int[][] grid, int[][] islandNumbers, int islandCount, int row, int column) { int size = 0; islandNumbers[row][column] = islandCount; int side = grid.length; Queue<int[]> queue = new LinkedList<int[]>(); queue.offer(new int[]{row, column}); while (!queue.isEmpty()) { int[] cell = queue.poll(); size++; int curRow = cell[0], curColumn = cell[1]; for (int[] direction : directions) { int newRow = curRow + direction[0], newColumn = curColumn + direction[1]; if (newRow >= 0 && newRow < side && newColumn >= 0 && newColumn < side && grid[newRow][newColumn] == 1 && islandNumbers[newRow][newColumn] == 0) { islandNumbers[newRow][newColumn] = islandCount; queue.offer(new int[]{newRow, newColumn}); } } } return size; } } ############ class Solution { private int n; private int[] p; private int[] size; private int ans = 1; private int[] dirs = new int[] {-1, 0, 1, 0, -1}; public int largestIsland(int[][] grid) { n = grid.length; p = new int[n * n]; size = new int[n * n]; for (int i = 0; i < p.length; ++i) { p[i] = i; size[i] = 1; } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) { int pa = find(x * n + y), pb = find(i * n + j); if (pa == pb) { continue; } p[pa] = pb; size[pb] += size[pa]; ans = Math.max(ans, size[pb]); } } } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 0) { int t = 1; Set<Integer> vis = new HashSet<>(); for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) { int root = find(x * n + y); if (!vis.contains(root)) { vis.add(root); t += size[root]; } } } ans = Math.max(ans, t); } } } return ans; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } -
// OJ: https://leetcode.com/problems/making-a-large-island/ // Time: O(MN) // Space: O(MN) class UnionFind { vector<int> id, size; public: UnionFind(int N) : id(N), size(N, 1) { iota(begin(id), end(id), 0); } int find(int x) { return id[x] == x ? x : (id[x] = find(id[x])); } void connect(int x, int y) { int p = find(x), q = find(y); if (p == q) return; id[p] = q; size[q] += size[p]; } int getSize(int x) { return size[find(x)]; } }; class Solution { public: int largestIsland(vector<vector<int>>& G) { int M = G.size(), N = G[0].size(), dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, ans = 0; UnionFind uf(M * N); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (G[i][j] == 0) continue; for (auto &[dx, dy] : dirs) { int x = i + dx, y = j + dy; if (x < 0 || y < 0 || x >= M || y >= N || G[x][y] == 0) continue; uf.connect(i * N + j, x * N + y); } ans = max(ans, uf.getSize(i * N + j)); } } for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (G[i][j] == 1) continue; unordered_map<int, int> m; for (auto &[dx, dy] : dirs) { int x = i + dx, y = j + dy; if (x < 0 || y < 0 || x >= M || y >= N || G[x][y] == 0) continue; m[uf.find(x * N + y)] = uf.getSize(x * N + y); } int size = 1; for (auto &p : m) size += p.second; ans = max(ans, size); } } return ans; } }; -
class Solution: def largestIsland(self, grid: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(a, b): pa, pb = find(a), find(b) if pa == pb: return p[pa] = pb size[pb] += size[pa] n = len(grid) p = list(range(n * n)) size = [1] * (n * n) for i, row in enumerate(grid): for j, v in enumerate(row): if v: for a, b in [[0, -1], [-1, 0]]: x, y = i + a, j + b if 0 <= x < n and 0 <= y < n and grid[x][y]: union(x * n + y, i * n + j) ans = max(size) for i, row in enumerate(grid): for j, v in enumerate(row): if v == 0: vis = set() t = 1 for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]: x, y = i + a, j + b if 0 <= x < n and 0 <= y < n and grid[x][y]: root = find(x * n + y) if root not in vis: vis.add(root) t += size[root] ans = max(ans, t) return ans -
func largestIsland(grid [][]int) int { n := len(grid) p := make([]int, n*n) size := make([]int, n*n) for i := range p { p[i] = i size[i] = 1 } var find func(int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } dirs := []int{-1, 0, 1, 0, -1} ans := 1 for i, row := range grid { for j, v := range row { if v == 1 { for k := 0; k < 4; k++ { x, y := i+dirs[k], j+dirs[k+1] if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1 { pa, pb := find(x*n+y), find(i*n+j) if pa != pb { p[pa] = pb size[pb] += size[pa] ans = max(ans, size[pb]) } } } } } } for i, row := range grid { for j, v := range row { if v == 0 { t := 1 vis := map[int]struct{}{} for k := 0; k < 4; k++ { x, y := i+dirs[k], j+dirs[k+1] if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1 { root := find(x*n + y) if _, ok := vis[root]; !ok { vis[root] = struct{}{} t += size[root] } } } ans = max(ans, t) } } } return ans } func max(a, b int) int { if a > b { return a } return b } -
function largestIsland(grid: number[][]): number { const n = grid.length; const vis = Array.from({ length: n }, () => new Array(n).fill(false)); const group = Array.from({ length: n }, () => new Array(n).fill(0)); const dfs = (i: number, j: number, paths: [number, number][]) => { if ( i < 0 || j < 0 || i === n || j === n || vis[i][j] || grid[i][j] !== 1 ) { return; } vis[i][j] = true; paths.push([i, j]); dfs(i + 1, j, paths); dfs(i, j + 1, paths); dfs(i - 1, j, paths); dfs(i, j - 1, paths); }; let count = 1; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { const paths: [number, number][] = []; dfs(i, j, paths); if (paths.length !== 0) { for (const [x, y] of paths) { group[x][y] = count; grid[x][y] = paths.length; } count++; } } } let res = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { let sum = grid[i][j]; if (grid[i][j] === 0) { sum++; const set = new Set(); if (i !== 0) { sum += grid[i - 1][j]; set.add(group[i - 1][j]); } if (i !== n - 1 && !set.has(group[i + 1][j])) { sum += grid[i + 1][j]; set.add(group[i + 1][j]); } if (j !== 0 && !set.has(group[i][j - 1])) { sum += grid[i][j - 1]; set.add(group[i][j - 1]); } if (j !== n - 1 && !set.has(group[i][j + 1])) { sum += grid[i][j + 1]; } } res = Math.max(res, sum); } } return res; } -
use std::collections::HashSet; impl Solution { fn dfs( i: usize, j: usize, grid: &Vec<Vec<i32>>, paths: &mut Vec<(usize, usize)>, vis: &mut Vec<Vec<bool>>, ) { let n = vis.len(); if vis[i][j] || grid[i][j] != 1 { return; } paths.push((i, j)); vis[i][j] = true; if i != 0 { Self::dfs(i - 1, j, grid, paths, vis); } if j != 0 { Self::dfs(i, j - 1, grid, paths, vis); } if i != n - 1 { Self::dfs(i + 1, j, grid, paths, vis); } if j != n - 1 { Self::dfs(i, j + 1, grid, paths, vis); } } pub fn largest_island(mut grid: Vec<Vec<i32>>) -> i32 { let n = grid.len(); let mut vis = vec![vec![false; n]; n]; let mut group = vec![vec![0; n]; n]; let mut count = 1; for i in 0..n { for j in 0..n { let mut paths: Vec<(usize, usize)> = Vec::new(); Self::dfs(i, j, &grid, &mut paths, &mut vis); let m = paths.len() as i32; if m != 0 { for (x, y) in paths { grid[x][y] = m; group[x][y] = count; } count += 1; } } } let mut res = 0; for i in 0..n { for j in 0..n { let mut sum = grid[i][j]; if grid[i][j] == 0 { sum += 1; let mut set = HashSet::new(); if i != 0 { sum += grid[i - 1][j]; set.insert(group[i - 1][j]); } if j != 0 && !set.contains(&group[i][j - 1]) { sum += grid[i][j - 1]; set.insert(group[i][j - 1]); } if i != n - 1 && !set.contains(&group[i + 1][j]) { sum += grid[i + 1][j]; set.insert(group[i + 1][j]); } if j != n - 1 && !set.contains(&group[i][j + 1]) { sum += grid[i][j + 1]; set.insert(group[i][j + 1]); } } res = res.max(sum); } } res } }