forked from Sunchit/Coding-Decoded
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMakingALargeIsland.java
More file actions
49 lines (41 loc) · 1.47 KB
/
MakingALargeIsland.java
File metadata and controls
49 lines (41 loc) · 1.47 KB
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
class Solution {
// TC : O(n2)
public int largestIsland(int[][] grid) {
// id, Area
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 0);
int n = grid.length;
int gridId = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int size = assignIdAndReturnArea(grid, i, j, gridId);
map.put(gridId, size);
gridId++;
}
}
}
int res = map.getOrDefault(2,0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
//We use a set to avoid repeatly adding islands with the same id
Set<Integer> set = new HashSet<>();
set.add(i > 0 ? grid[i - 1][j] : 0);
set.add(i < n - 1 ? grid[i + 1][j] : 0);
set.add(j > 0 ? grid[i][j - 1] : 0);
set.add(j < n - 1 ? grid[i][j + 1] : 0);
int totalArea = 1; //We need to count current island as well
for (int id : set) totalArea += map.get(id);
res = Math.max(res, totalArea);
}
}
}
return res;
}
private int assignIdAndReturnArea(int[][] grid, int i, int j, int id) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != 1) return 0;
grid[i][j] = id;
return 1 + assignIdAndReturnArea(grid, i + 1, j, id) + assignIdAndReturnArea(grid, i - 1, j, id) + assignIdAndReturnArea(grid, i, j + 1, id) + assignIdAndReturnArea(grid, i, j - 1, id);
}
}