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.
1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4
5class Solution {
6public:
7 int largestIsland(std::vector<std::vector<int>>& grid) {
8 int n = grid.size();
9 int index = 2;
10 std::unordered_map<int, int> areaMap;
11
12 for (int i = 0; i < n; i++) {
13 for (int j = 0; j < n; j++) {
14 if (grid[i][j] == 1) {
15 int area = dfs(grid, i, j, index);
16 areaMap[index] = area;
17 index++;
18 }
19 }
20 }
21
22 int maxArea = 0;
23 for (const auto& [key, value] : areaMap) {
24 maxArea = std::max(maxArea, value);
25 }
26
27 std::vector<std::pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
28
29 for (int i = 0; i < n; i++) {
30 for (int j = 0; j < n; j++) {
31 if (grid[i][j] == 0) {
32 std::unordered_set<int> seen;
33 int area = 1;
34 for (auto [di, dj] : directions) {
35 int ni = i + di, nj = j + dj;
36 if (ni >= 0 && nj >= 0 && ni < n && nj < n) {
37 int idx = grid[ni][nj];
38 if (idx > 1) {
39 seen.insert(idx);
40 }
41 }
42 }
43 for (int idx : seen) {
44 area += areaMap[idx];
45 }
46 maxArea = std::max(maxArea, area);
47 }
48 }
49 }
50 return maxArea;
51 }
52
53 int dfs(std::vector<std::vector<int>>& grid, int i, int j, int index) {
54 int n = grid.size();
55 grid[i][j] = index;
56 int area = 1;
57 std::vector<std::pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
58 for (auto [di, dj] : directions) {
59 int ni = i + di, nj = j + dj;
60 if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1) {
61 area += dfs(grid, ni, nj, index);
62 }
63 }
64 return area;
65 }
66};The C++ implementation follows a similar pattern. Using a DFS to mark and calculate the areas of islands, a hashmap is constructed to store these values using index labels.
Potential large islands are computed by considering the neighboring cells around '0's, aggregating unique island contributions using a hashset to ensure no duplication.