Massive Algorithms: LeetCode 827 - Making A Large Island

LeetCode 827 - Making A Large Island

https://leetcode.com/problems/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

As in the previous solution, we check every 0. However, we also store the size of each group, so that we do not have to use depth-first search to repeatedly calculate the same size.

However, this idea fails when the 0 touches the same group. For example, consider grid = [[0,1],[1,1]]. The answer is 4, not 1 + 3 + 3, since the right neighbor and the bottom neighbor of the 0belong to the same group.

We can remedy this problem by keeping track of a group id (or index), that is unique for each group. Then, we'll only add areas of neighboring groups with different ids.

Algorithm

For each group, fill it with value index and remember it's size as area[index] = dfs(...).

Then for each 0, look at the neighboring group ids seen and add the area of those groups, plus 1 for the 0 we are toggling. This gives us a candidate answer, and we take the maximum.

To solve the issue of having potentially no 0, we take the maximum of the previously calculated areas.

Time Complexity: $O(N^2)$ , where $N$ is the length and width of the grid.

int[] dr = new int[] { -1, 0, 1, 0 };

int[] dc = new int[] { 0, -1, 0, 1 };

int[][] grid;

int N;

public int largestIsland(int[][] grid) {

this.grid = grid;

N = grid.length;

int index = 2;

int[] area = new int[N * N + 2];

for (int r = 0; r < N; ++r)

for (int c = 0; c < N; ++c)

if (grid[r][c] == 1)

area[index] = dfs(r, c, index++);

int ans = 0;

for (int x : area)

ans = Math.max(ans, x);

for (int r = 0; r < N; ++r)

for (int c = 0; c < N; ++c)

if (grid[r][c] == 0) {

Set<Integer> seen = new HashSet();

for (Integer move : neighbors(r, c))

if (grid[move / N][move % N] > 1)

seen.add(grid[move / N][move % N]);

int bns = 1;

for (int i : seen)

bns += area[i];

ans = Math.max(ans, bns);

}

return ans;

}

public int dfs(int r, int c, int index) {

int ans = 1;

grid[r][c] = index;

for (Integer move : neighbors(r, c)) {

if (grid[move / N][move % N] == 1) {

grid[move / N][move % N] = index;

ans += dfs(move / N, move % N, index);

}

return ans;

}

public List<Integer> neighbors(int r, int c) {

List<Integer> ans = new ArrayList();

for (int k = 0; k < 4; ++k) {

int nr = r + dr[k];

int nc = c + dc[k];

if (0 <= nr && nr < N && 0 <= nc && nc < N)

ans.add(nr * N + nc);

}

return ans;

}

X.
https://leetcode.com/problems/making-a-large-island/discuss/126960/Extremely-Simple-Concept-Using-Marker

Mark all the Connected Components in the grid using a distinct Integer marker.

Keep the count of the marker in the grid using a HashMap.

For each zero check the distinct islands that get connected.

ex:

101
000
011

using Marker
Grid :
203
000
044

Map :
2 : 1
3 : 1
4 : 2

Now for each zero, check the distinct marker it connects.
The zero in the 2nd row last column connects marker 3 and 4.

Hence the counts becomes maximum = 2 (count of 4) + 1 (count of 3) + 1(The zero that is converted to 1).

https://leetcode.com/problems/making-a-large-island/discuss/127015/C%2B%2B-O(n*m)-15-ms-colorful-islands
https://leetcode.com/problems/making-a-large-island/discuss/127032/C%2B%2BJavaPython-Straight-Forward-O(N2)-with-Explanations

For each 1 in the grid, we paint all connected 1 with the next available color (2, 3, and so on). We also remember the size of the island we just painted with that color.

Then, we analyze all 0 in the grid, and sum sizes of connected islands (based on the island color). Note that the same island can connect to 0 more than once. The example below demonstrates this idea (the answer is highlighted):

    public int largestIsland(int[][] grid) {
        Map<Integer, Integer> map = new HashMap<>(); //Key: color, Val: size of island painted of that color
        map.put(0, 0); //We won't paint island 0, hence make its size 0, we will use this value later   
        int n = grid.length; 
        int colorIndex = 2; //0 and 1 is already used in grid, hence we start colorIndex from 2 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int size = paint(grid, i, j, colorIndex);
                    map.put(colorIndex, size);
                    colorIndex++;
                }
            }
        }
    
        //If there is no island 0 from grid, res should be the size of islands of first color
        //If there is no island 1 from grid, res should be 0 
        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 color
                    Set<Integer> set = new HashSet<>();
                    //If current island is at the boundary, we add 0 to the set, whose value is 0 in the map
                    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 newSize = 1; //We need to count current island as well, hence we init newSize with 1
                    for (int color : set) newSize += map.get(color);
                    res = Math.max(res, newSize);
                }
            }
        }
        return res;
    }
    
    //Helper method to paint current island and all its connected neighbors
    //Return the size of all painted islands at the end
    private int paint(int[][] grid, int i, int j, int color) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != 1) return 0;
        grid[i][j] = color;
        return 1 + paint(grid, i + 1, j, color) + paint(grid, i - 1, j, color) + paint(grid, i, j + 1, color) + paint(grid, i, j - 1, color);
    }

X. Union Find
https://leetcode.com/problems/making-a-large-island/discuss/157446/JAVA-UnoinFind-O(mn)

class UnionFind {
    
    private int[] id;
    private int[] size;
    
    public UnionFind(int[][] grid) {
        
        int m = grid.length, n = grid[0].length;
        this.id = new int[m * n];
        this.size = new int[m * n];
        
        for (int i = 0; i < m * n; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }
    
    private int find(int i) {
    
        while (id[i] != i) {
            i = id[i];
            id[i] = id[id[i]];
        }

        return i;
    }

    private boolean isConnected(int p, int q) {

        return find(p) == find(q);
    }

    private void union(int p, int q) {

        int rp = find(p), rq = find(q);
        if (rp == rq)
            return;
        else if (size[rp] > size[rq]) {
            id[rq] = rp;
            size[rp] += size[rq];
        } else {
            id[rp] = rq;
            size[rq] += size[rp];
        }
    }
}

private UnionFind uf;
private int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public int largestIsland(int[][] grid) {
    
    int m = grid.length, n = grid[0].length;
    int max = Integer.MIN_VALUE;
    uf = new UnionFind(grid);
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0)
                continue;
            for (int[] dir : dirs) {
                int ni = i + dir[0];
                int nj = j + dir[1];
                if (ni < 0 || nj < 0 || ni >= m || nj >= n || grid[ni][nj] == 0)
                    continue;
                if (!uf.isConnected(i * n + j, ni * n + nj)) {
                    uf.union(i * n + j, ni * n + nj);
                }
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                int root = uf.find(i * n + j);
                max = Math.max(max, uf.size[root]);
            } else {
                Set<Integer> visited = new HashSet<>();
                int sum = 1;
                for (int[] dir : dirs) {
                    int ni = i + dir[0];
                    int nj = j + dir[1];
                    if (ni < 0 || nj < 0 || ni >= m || nj >= n || grid[ni][nj] == 0)
                        continue;
                    int root = uf.find(ni * n + nj);
                    if (visited.add(root)) {
                        sum += uf.size[root];
                    }
                }
                max = Math.max(max, sum);
            }
        }
    }
    
    return max;
}

X. https://leetcode.com/problems/making-a-large-island/discuss/127256/DFS-JAVA-AC-CONCISE-SOLUTION

For each 0, change it to a 1, then do a depth first search to find the size of that component. The answer is the maximum size component found.

Of course, if there is no 0 in the grid, then the answer is the size of the whole grid.

Time Complexity: $O(N^4)$ , where $N$ is the length and width of the grid.
Space Complexity: $O(N^2)$ , the additional space used in the depth first search by stack and seen.

int[] dr = new int[] { -1, 0, 1, 0 };

int[] dc = new int[] { 0, -1, 0, 1 };

public int largestIsland(int[][] grid) {

int N = grid.length;

int ans = 0;

boolean hasZero = false;

for (int r = 0; r < N; ++r)

for (int c = 0; c < N; ++c)

if (grid[r][c] == 0) {

hasZero = true;

grid[r][c] = 1;

ans = Math.max(ans, check(grid, r, c));

grid[r][c] = 0;

}

return hasZero ? ans : N * N;

}

public int check(int[][] grid, int r0, int c0) {

int N = grid.length;

Stack<Integer> stack = new Stack();

Set<Integer> seen = new HashSet();

stack.push(r0 * N + c0);

seen.add(r0 * N + c0);

while (!stack.isEmpty()) {

int code = stack.pop();

int r = code / N, c = code % N;

for (int k = 0; k < 4; ++k) {

int nr = r + dr[k], nc = c + dc[k];

if (!seen.contains(nr * N + nc) && 0 <= nr && nr < N && 0 <= nc && nc < N && grid[nr][nc] == 1) {

stack.push(nr * N + nc);

seen.add(nr * N + nc);

}

return seen.size();

}

LeetCode 827 - Making A Large Island

Labels

Popular Posts