Sponsored
Sponsored
This approach involves two main steps: firstly labeling all the islands in the grid using DFS, and secondly calculating the maximum possible island size by changing a '0' to a '1'.
1. Traverse the grid using DFS and label each island with a unique identifier. As you label the islands, keep track of the size of each island in a dictionary.
2. Iterate over each '0' cell in the grid, consider changing it to '1', and calculate the potential island size by inspecting neighboring cells.
3. Use a set to aggregate the neighboring island labels, and use the sizes from the dictionary to compute the total size.
This allows us to efficiently calculate the new island sizes by directly accessing individual island sizes using their labels.
Time Complexity: O(n^2), because each cell of the grid is visited at most twice, once for DFS and once for change evaluation.
Space Complexity: O(n^2) for storage of the labeled grid and area dictionary.
1class Solution {
2 private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
3
4 public int largestIsland(int[][] grid) {
5 int n = grid.length;
6 Map<Integer, Integer> areaMap = new HashMap<>();
7 int index = 2;
8 for (int i = 0; i < n; i++) {
9 for (int j = 0; j < n; j++) {
10 if (grid[i][j] == 1) {
11 int area = dfs(grid, i, j, index);
12 areaMap.put(index, area);
13 index++;
14 }
15 }
16 }
17
18 int maxArea = areaMap.values().stream().max(Integer::compare).orElse(0);
19
20 for (int i = 0; i < n; i++) {
21 for (int j = 0; j < n; j++) {
22 if (grid[i][j] == 0) {
23 Set<Integer> seen = new HashSet<>();
24 int newArea = 1;
25 for (int[] d : directions) {
26 int ni = i + d[0], nj = j + d[1];
27 if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] > 1 && seen.add(grid[ni][nj])) {
28 newArea += areaMap.get(grid[ni][nj]);
29 }
30 }
31 maxArea = Math.max(maxArea, newArea);
32 }
33 }
34 }
35
36 return maxArea;
37 }
38
39 private int dfs(int[][] grid, int i, int j, int index) {
40 grid[i][j] = index;
41 int area = 1;
42 for (int[] dir : directions) {
43 int ni = i + dir[0], nj = j + dir[1];
44 if (ni >= 0 && nj >= 0 && ni < grid.length && nj < grid[0].length && grid[ni][nj] == 1) {
45 area += dfs(grid, ni, nj, index);
46 }
47 }
48 return area;
49 }
50}The Java solution mirrors the logic of the Python solution, using a DFS helper method to explore and mark islands with unique indices. A HashMap stores the size of each island.
For each '0', its contribution to a possible larger island is calculated by evaluating surrounding marked areas, and potentially updating the maximum island size found.