LeetCode 827: Making A Large Island
Problem Description
Explanation:
To solve this problem, we can follow these steps:
- Perform a Depth First Search (DFS) to label each island with a unique number and calculate its area. We can create a map to store the area of each island.
- Iterate over each '0' cell in the grid. For each '0' cell, check the unique island labels of its neighboring cells and calculate the total area if we change the '0' cell to '1'.
- Keep track of the maximum island area found during step 2.
Time Complexity: O(n^2) where n is the size of the grid. Space Complexity: O(n^2) for the island labeling map.
:
Solutions
class Solution {
public int largestIsland(int[][] grid) {
int n = grid.length;
Map<Integer, Integer> areaMap = new HashMap<>();
int islandIndex = 2; // Starting index for island labeling
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int area = dfs(grid, i, j, islandIndex);
areaMap.put(islandIndex, area);
islandIndex++;
}
}
}
int maxArea = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
Set<Integer> neighborIslands = new HashSet<>();
if (i > 0) neighborIslands.add(grid[i - 1][j]);
if (i < n - 1) neighborIslands.add(grid[i + 1][j]);
if (j > 0) neighborIslands.add(grid[i][j - 1]);
if (j < n - 1) neighborIslands.add(grid[i][j + 1]);
int totalArea = 1; // Current '0' cell turned to '1'
for (int island : neighborIslands) {
totalArea += areaMap.getOrDefault(island, 0);
}
maxArea = Math.max(maxArea, totalArea);
}
}
}
return maxArea == 0 ? n * n : maxArea;
}
private int dfs(int[][] grid, int i, int j, int islandIndex) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
return 0;
}
grid[i][j] = islandIndex;
return 1 + dfs(grid, i - 1, j, islandIndex) + dfs(grid, i + 1, j, islandIndex)
+ dfs(grid, i, j - 1, islandIndex) + dfs(grid, i, j + 1, islandIndex);
}
}Related LeetCode Problems
Loading editor...