Count Sub Islands

Medium · Graphs · Explanation and code example

Disjoint Set Union

How it works

We can use Union-Find to group connected land cells in grid2 into islands. The key insight is that we also create a special "invalid" node (indexed at N, where N is the total number of cells). Any land cell in grid2 that corresponds to water in grid1 gets unioned with this invalid node. After processing, the number of sub-islands equals the total land cells minus the number of union operations performed (since each union either merges two components or marks one as invalid).

Steps

  1. Initialize a DSU with N+1 nodes (N cells plus one invalid node).
  2. For each land cell in grid2:
    • Count it as a land cell.
    • Union it with its right neighbor if the neighbor is also land in grid2.
    • Union it with its bottom neighbor if the neighbor is also land in grid2.
    • If grid1 has water at this position, union this cell with the invalid node N.
  3. Track the number of successful unions (where two different components merge).
  4. Return land count minus union count, which gives the number of valid sub-islands.

Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

Where m is the number of rows and n is the number of columns.

Things to watch for

Returning Early When a Mismatch is Found

A critical mistake is returning false immediately when finding a cell that exists in grid2 but not in grid1. This leaves part of the island unexplored and unvisited, causing those cells to be counted as separate islands later.

Using OR Instead of AND for Recursive Results

When combining results from the four directional DFS calls, using OR (|) instead of AND (&) will incorrectly mark an island as a sub-island if any single cell matches, rather than requiring all cells to match.

Checking the Wrong Grid for Land Cells

When deciding whether to explore a neighboring cell, the check must be against grid2 (where we're finding islands), not grid1. The grid1 check determines validity, but grid2 determines connectivity.

Python code example

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] < self.Size[pv]:
            pu, pv = pv, pu
        self.Size[pu] += self.Size[pv]
        self.Parent[pv] = pu
        return True

class Solution:
    def countSubIslands(self, grid1, grid2):
        ROWS, COLS = len(grid1), len(grid1[0])
        N = ROWS * COLS
        dsu = DSU(N)

        def getId(r, c):
            return r * COLS + c

        land = unions = 0
        for r in range(ROWS):
            for c in range(COLS):
                if not grid2[r][c]:
                    continue
                land += 1
                if r + 1 < ROWS and grid2[r + 1][c]:
                    unions += dsu.union(getId(r, c), getId(r + 1, c))
                if c + 1 < COLS and grid2[r][c + 1]:
                    unions += dsu.union(getId(r, c), getId(r, c + 1))
                if not grid1[r][c]:
                    unions += dsu.union(getId(r, c), N)

        return land - unions

C++ code example

class DSU {
    vector<int> Parent, Size;

public:
    DSU(int n) {
        Parent.resize(n + 1);
        Size.assign(n + 1, 1);
        for (int i = 0; i <= n; i++) Parent[i] = i;
    }

    int find(int node) {
        if (Parent[node] != node) Parent[node] = find(Parent[node]);
        return Parent[node];
    }

    bool unionSets(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return false;
        if (Size[pu] < Size[pv]) swap(pu, pv);
        Size[pu] += Size[pv];
        Parent[pv] = pu;
        return true;
    }
};

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int ROWS = grid1.size(), COLS = grid1[0].size(), N = ROWS * COLS;
        DSU dsu(N);

        int land = 0, unions = 0;
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (!grid2[r][c]) continue;
                land++;
                if (r + 1 < ROWS && grid2[r + 1][c])
                    unions += dsu.unionSets(r * COLS + c, (r + 1) * COLS + c);
                if (c + 1 < COLS && grid2[r][c + 1])
                    unions += dsu.unionSets(r * COLS + c, r * COLS + c + 1);
                if (!grid1[r][c])
                    unions += dsu.unionSets(r * COLS + c, N);
            }
        }
        return land - unions;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations