leetcode 827 - Making A Large Island

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
class Solution {
public:
vector<int> leader;
vector<int> total;

int largestIsland(vector<vector<int>>& grid) {
int row = grid.size(), col = grid[0].size();
int size = row * col;

leader.resize(size);
total.resize(size, 1);

for (int i = 0; i < size; i++) {
leader[i] = i;
}

vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (grid[r][c] == 1) {
for (auto d : dirs) {
int rr = r + d[0];
int cc = c + d[1];

if (rr < 0 || rr >= row || cc < 0 || cc >= col || grid[rr][cc] == 0)
continue;

Union(find(r*row + c), find(rr*row + cc));
}
}
}
}

int max_island = 0;
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (grid[r][c] == 0) {
unordered_set<int> set;

for (auto d : dirs) {
int rr = r + d[0];
int cc = c + d[1];

if (rr < 0 || rr >= row || cc < 0 || cc >= col || grid[rr][cc] == 0)
continue;

set.insert(find(rr * row + cc));
}

int cnt = 1;
for (auto i : set)
cnt += total[i];

max_island = max(max_island, cnt);
}
}
}

return max_island == 0 ? size : max_island;
}

int find(int i) {
if (leader[i] != i)
leader[i] = find(leader[i]);

return leader[i];
}

void Union(int i, int j) {
int x = leader[i];
int y = leader[j];

if (x == y) return;

leader[x] = y;
total[y] += total[x];
}
};

class Solution2 {
public:
int largestIsland(vector<vector<int>>& grid) {
int row = grid.size(), col = grid[0].size();

vector<vector<bool>> seen(row, vector<bool>(col, false));
vector<vector<int>> ids(row, vector<int>(col));
unordered_map<int, int> maps;
int max_islands = 0;

int id = 0;

for (int r = 0; r < row; r++) {
for (int c = 0; c < row; c++) {
if (grid[r][c] == 0 || seen[r][c] == true)
continue;

int total = 0;
dfs(grid, r, c, seen, total, ids, id);
maps[id] = total;
max_islands = max(max_islands, total);
id++;
}
}

vector<vector<int>> dirs = {{0,1}, {1,0}, {-1,0}, {0,-1}};

for (int r = 0; r < row; r++) {
for (int c = 0; c < row; c++) {
if (grid[r][c] == 0) {
unordered_set<int> sets;

for (auto &dir : dirs) {
int x = r + dir[0];
int y = c + dir[1];

if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == 0)
continue;

int id = ids[x][y];
sets.insert(id);
}

int islands = 1;
for (int id : sets)
islands += maps[id];

max_islands = max(max_islands, islands);
}
}
}

return max_islands;
}

void dfs(vector<vector<int>>& grid, int r, int c,
vector<vector<bool>> &seen, int &total, vector<vector<int>> &ids, int id) {

int row = grid.size(), col = grid[0].size();

vector<vector<int>> dirs = {{0,1}, {1,0}, {-1,0}, {0,-1}};

seen[r][c] = true;
total++;
ids[r][c] = id;

for (auto &dir : dirs) {
int x = r + dir[0];
int y = c + dir[1];

if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == 0 || seen[x][y] == true)
continue;

dfs(grid, x, y, seen, total, ids, id);
}
}
};