Making A Large Island LeetCode solution in Java

1
class Solution {
2
  int dir[][] =
3
      new int[][] {
4
        {1, 0},
5
        {-1, 0},
6
        {0, 1},
7
        {0, -1}
8
      };
9

10
  private int countArea(int grid[][], int i, int j, int num) {
11
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return 0;
12

13
    if (grid[i][j] != 1) return 0;
14

15
    grid[i][j] = num;
16
    int count = 0;
17
    for (int d[] : dir) {
18
      count += countArea(grid, i + d[0], j + d[1], num);
19
    }
20

21
    return 1 + count;
22
  }
23

24
  private void fillDP(int grid[][], int dp[][], int i, int j, int count, int num) {
25
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return;
26

27
    if (grid[i][j] != num) return;
28

29
    if (dp[i][j] != 0) return;
30
    dp[i][j] = count;
31
    for (int d[] : dir) {
32
      fillDP(grid, dp, i + d[0], j + d[1], count, num);
33
    }
34
  }
35

36
  public int largestIsland(int[][] grid) {
37
    int n = grid.length, m = grid[0].length;
38
    int dp[][] = new int[n][m];
39

40
    int num = 1;
41
    for (int i = 0; i < n; ++i) {
42
      for (int j = 0; j < m; ++j) {
43
        if (grid[i][j] == 1) {
44
          ++num;
45
          int count1 = countArea(grid, i, j, num);
46
          fillDP(grid, dp, i, j, count1, num);
47
        }
48
      }
49
    }
50

51
    int max = 0;
52
    for (int i = 0; i < n; ++i) {
53
      for (int j = 0; j < m; ++j) {
54
        if (grid[i][j] != 0) continue;
55
        int val = 1;
56
        Set<Integer> set = new HashSet<>();
57
        for (int d[] : dir) {
58
          int newRow = i + d[0];
59
          int newCol = j + d[1];
60

61
          if (newRow < 0 || newRow >= n || newCol < 0 || newCol >= m) continue;
62
          if (set.contains(grid[newRow][newCol])) continue;
63

64
          val += dp[newRow][newCol];
65
          set.add(grid[newRow][newCol]);
66
        }
67
        max = Math.max(max, val);
68
      }
69
    }
70

71
    if (max == 0) return n * m;
72
    return max;
73
  }
74
}