827 - Making A Large Island
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Return the size of the largest island in grid after applying this operation.
An island is a 4-directionally connected group of 1s.
Example 1:
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.
Example 2:
Input: grid = [[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: grid = [[1,1],[1,1]] Output: 4 Explanation: Can't change any 0 to 1, only one island with area = 4.
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j]is either0or1.
Solutions
Union find.
JAVA
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]; } }
C++
class Solution { public: const static inline vector<int> dirs = {-1, 0, 1, 0, -1}; int largestIsland(vector<vector<int>>& grid) { int n = grid.size(); vector<int> p(n * n); vector<int> size(n * n, 1); iota(p.begin(), p.end(), 0); function<int(int)> find; find = [&](int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; }; int ans = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j]) { 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]) { int pa = find(x * n + y), pb = find(i * n + j); if (pa == pb) continue; p[pa] = pb; size[pb] += size[pa]; ans = max(ans, size[pb]); } } } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (!grid[i][j]) { int t = 1; unordered_set<int> vis; 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]) { int root = find(x * n + y); if (!vis.count(root)) { vis.insert(root); t += size[root]; } } } ans = max(ans, t); } } } return ans; } };
PYTHON
from collections import defaultdict class Solution: def largestIsland(self, grid): n = len(grid) parent = {i: i for i in range(n * n)} size = {i: 1 for i in range(n * n)} dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(x, y): root_x, root_y = find(x), find(y) if root_x != root_y: parent[root_x] = root_y size[root_y] += size[root_x] # Step 1: Connect components of '1's using union-find for i in range(n): for j in range(n): if grid[i][j] == 1: index = i * n + j for dx, dy in dirs: ni, nj = i + dx, j + dy if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1: union(index, ni * n + nj) # Step 2: Find the largest island before flipping any zero max_island = max(size.values()) if size else 0 # Step 3: Try flipping each '0' and calculate possible max island for i in range(n): for j in range(n): if grid[i][j] == 0: seen_roots = set() new_size = 1 for dx, dy in dirs: ni, nj = i + dx, j + dy if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1: root = find(ni * n + nj) if root not in seen_roots: seen_roots.add(root) new_size += size[root] max_island = max(max_island, new_size) return max_island
Comments
Post a Comment