[Leetcode] Problem 827 - Making A Large Island

Posted on | In ,

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

No.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.

No.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.

No.3

Input: [[1, 1], [1, 1]]

Output: 4

Explanation: Can’t change any 0 to 1, only one island with area = 4.

Note

  • 1 <= grid.length = grid[0].length <= 50.
  • 0 <= grid[i][j] <= 1.

Code

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
private int m;
private int n;
private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int largestIsland(int[][] grid) {
    int result = 0;
    int index = 2;
    m = grid.length;
    n = grid[0].length;
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                int area = getArea(grid, i, j, index);
                map.put(index, area);
                result = Math.max(area, result);
                index++;
            }
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                Set<Integer> set = new HashSet<>();
                int area = 1;

                for (int[] dir : dirs) {
                    int idx = getIndex(grid, i + dir[0], j + dir[1]);

                    if (idx != 0 && !set.contains(idx))
                        area += map.get(idx);

                    set.add(idx);
                }

                result = Math.max(area, result);
            }
        }
    }

    return result;
}

private int getArea(int[][] grid, int x, int y, int index) {
    if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1)
        return 0;

    grid[x][y] = index;
    int area = 1;

    for (int[] dir : dirs)
        area += getArea(grid, x + dir[0], y + dir[1], index);

    return area;
}

private int getIndex(int[][] grid, int x, int y) {
    if (x < 0 || y < 0 || x >= m || y >= n)
        return 0;

    return grid[x][y];
}