LC: 305. Number of Islands II - spiralgo/algorithms GitHub Wiki

305. Number of Islands II:

The Essence:

When we add a new land; in some cases, it can decrease the total number of islands. Because it can connect two distinct islands as a united component.

This reminds a quote by @ErdemT09, in the PR https://github.com/spiralgo/algorithms/pull/200:

It is important to understand that:

If a new given edge connects 2 previously discrete nodes, then the number of connected components decreases.

It means, this question can be interpreted as a variant of https://github.com/spiralgo/algorithms/pull/200 and we can use Union-find here as well.

Details:

We use almost the same code with https://github.com/spiralgo/algorithms/pull/200. This time, instead of edge pairs of nodes, we have x, y positions array. Therefore, we need to generate edges (neighbors for this question) list using these positions. We can interpret each tile in the grid, as a node. We need a getNodeId method to convert a position into a node-id. In this case, an edge is only possible between a node and its valid adjacent nodes. It is why we need the DIRECTIONS array.

You can find the detailed explanation and implementation here: https://github.com/spiralgo/algorithms/pull/329