Topic description

This is on LeetCode 827. The Largest Artificial Island , the difficulty is Difficult.

Tag : "union set", "enumeration"

gives you a binary matrix grid of size n x n. At most one square 0 can be turned into a 1 .

After doing this, what is the area of ​​the largest island in the grid?

An island is formed by a set of 1's connected in four directions: up, down, left, and right.

Example 1:

enter: grid = [[1, 0], [0, 1]]

output: 3

explain: Turn a square 0 into a 1, and finally connect two small islands to get an island with an area of ​​3.

Example 2:

enter: grid = [[1, 1], [1, 0]]

output: 4

explain: Turn a square 0 into a 1, and expand the area of ​​the island to 4.

Example 3:

enter: grid = [[1, 1], [1, 1]]

output: 4

explain: There is no 0 to make us a 1, and the area is still 4.

hint:

• $n = grid.length$
• $n == grid[i].length$
• $1 <= n <= 500$
• grid[i][j] is either 0 or 1

union lookup + enumeration

For convenience, we let grid be g.

According to the meaning of the question, it is easy to think of maintaining the size of all connected blocks through "union search", and then through "enumeration" to find the optimal flip point.

Specifically, we can use Union Search to maintain all $g[i][j] = 1$block connectivity first, and in the process of maintaining connectivity, use sz[idx] to record the size of each connected block (note: only the root number of the connected block makes sz[idx] meaningful, that is, only sz[find(x)]).

Then we traverse g again and process them separately according to the original $g[i][j]$ value:

• If $g[i][j] = 1$, the location will not be used as a flip point, but the true maximum area is not necessarily caused by the flip (possibly from the original connectivity block), so we need to include $sz[root]$in the comparison, where root is the root node number of the connectivity block to which $(i, j)$belongs;
• If $g[i][j] = 0$, the location can be used as a flip point, and we can count the total size of the connected blocks corresponding to its four-way connection location to tot (note that if there are identical connected blocks in the direction of the four-way connection, only once), then $tot + 1$is the size of the new connected blocks resulting from flipping the location.

Finally, taking the maximum value of all connected block sizes is the answer.

Some details: for convenience, we let the numbering of the point $(i, j)$ start at $1$;
At the same time, when we need to use the SZ array, we can add the "rank-by-rank merge" of the union search set at will. Reflected in union operations, we always combine small connected blocks onto large ones to ensure that we are able to find a single operation with a complexity of $O(\alpha(n)$(can be seen as a constant), even in the worst case. It should be noted that only when "path compression" and "merge by rank" are applied at the same time, the complexity of the set search operation is $O (\alpha(n))$.

Java code:

class Solution {
    static int N = 510;
    static int[] p = new int[N * N], sz = new int[N * N];
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return ;
        if (sz[ra] > sz[rb]) {
            union(b, a);
        } else {
            sz[rb] += sz[ra]; p[ra] = p[rb];
        }
    }
    public int largestIsland(int[][] g) {
        int n = g.length;
        for (int i = 1; i <= n * n; i++) {
            p[i] = i; sz[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 0) continue;
                for (int[] di : dirs) {
                    int x = i + di[0], y = j + di[1];
                    if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue;
                    union(i * n + j + 1, x * n + y + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) {
                    ans = Math.max(ans, sz[find(i * n + j + 1)]);
                } else {
                    int tot = 1;
                    Set<Integer> set = new HashSet<>();
                    for (int[] di : dirs) {
                        int x = i + di[0],y = j + di[1];
                        if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue;
                        int root = find(x * n + y + 1);
                        if (set.contains(root)) continue;
                        tot += sz[root];
                        set.add(root);
                    }
                    ans = Math.max(ans, tot);
                }
            }
        }
        return ans;
    }
}

TypeScript code:

const N = 510
const p = new Array<number>(N * N).fill(-1), sz = new Array<number>(N * N).fill(1)
const dirs = [[1,0], [-1,0], [0,1], [0,-1]]
function find(x: number): number {
    if (p[x] != x) p[x] = find(p[x])
    return p[x]
}
function union(a: number, b: number): void {
    const ra = find(a), rb = find(b)
    if (ra == rb) return 
    if (sz[ra] > sz[rb]) {
        union(rb, ra)
    } else {
        sz[rb] += sz[ra]; p[ra] = p[rb]
    }
}
function largestIsland(g: number[][]): number {
    const n = g.length
    for (let i = 1; i <= n * n; i++) {
        p[i] = i; sz[i] = 1
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (g[i][j] == 0) continue
            for (const di of dirs) {
                const x = i + di[0], y = j + di[1]
                if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue
                union(i * n + j + 1, x * n + y + 1)
            }
        }
    }
    let ans = 0
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (g[i][j] == 1) {
                ans = Math.max(ans, sz[find(i * n + j + 1)])
            } else {
                let tot = 1
                const set = new Set()
                for (let di of dirs) {
                    const x = i + di[0], y = j + di[1]
                    if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue
                    const root = find(x * n + y + 1)
                    if (set.has(root)) continue
                    tot += sz[root]
                    set.add(root)
                }
                ans = Math.max(ans, tot)
            }
        }
    }
    return ans
};

Python code:

class Solution:
    def find(self, p, x):
        if p[x] != x:
            p[x] = self.find(p, p[x])
        return p[x]

    def union(self, p, sz, a, b):
        ra, rb = self.find(p, a), self.find(p, b)
        if ra == rb:
            return 
        if sz[ra] > sz[rb]:
            ra, rb = rb, ra
        sz[rb] += sz[ra]
        p[ra] = p[rb]

    def largestIsland(self, g: List[List[int]]) -> int:
        n, ans = len(g), 0
        p, sz = [i for i in range(n * n + 10)], [1 for _ in range(n * n + 10)]
        dirs = [[1,0],[-1,0],[0,1],[0,-1]]
        for i in range(n):
            for j in range(n):
                if g[i][j] == 0:
                    continue
                for di in dirs:
                    x, y = i + di[0], j + di[1]
                    if x < 0 or x >= n or y < 0 or y >= n or g[x][y] == 0:
                        continue
                    self.union(p, sz, i * n + j + 1, x * n + y + 1)
        for i in range(n):
            for j in range(n):
                if g[i][j] == 1:
                    ans = max(ans, sz[self.find(p, i * n + j + 1)])
                else:
                    tot = 1
                    vis = set()
                    for di in dirs:
                        x, y = i + di[0], j + di[1]
                        if x < 0 or x >= n or y < 0 or y >= n or g[x][y] == 0:
                            continue
                        root = self.find(p, x * n + y + 1)
                        if root in vis:
                            continue
                        tot += sz[root]
                        vis.add(root)
                    ans = max(ans, tot)
        return ans

• Time complexity: $O(n^2)$
• Space complexity: $O(n^2)$

at last

This is No.827 of our "Brush through LeetCode" series, starting in 2021/01/01. There are 1916 titles on LeetCode as of the start date, some of which are all locked. We will start with all Finished the topics with the lock.

In this series of articles, in addition to explaining the problem-solving ideas, the most concise code will be given as much as possible. If general solutions are involved, corresponding code templates will also be provided.

In order to facilitate the students to debug and submit code on the computer, I have established relevant warehouses: https://github.com/SharingSou... .

In the warehouse address, you can see the link to the solution of the series of articles, the corresponding code of the series of articles, the link to the original question of LeetCode and other preferred solutions.

For more, more comprehensive and more popular "Written Test/Interview" related information, please visit the beautifully typed Collection new base 🎉🎉

This article is by mdnice Multi-platform release