Number of Islands II

Problem#

Given an m x n water grid and a list of positions adding land cells one by one, return after each addition the current count of islands (4-connected land components).

Examples#

m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]] → [1,1,2,3].
m = 1, n = 1, positions = [[0,0]] → [1].

Constraints#

1 <= m, n, positions.length <= 10^4.

Hints#

Hint

DSU with running count: adding a cell increments by 1, unioning with each new neighbor decrements by 1.

Approach#

Initialize DSU and count = 0. For each position: if already land, skip with current count. Otherwise mark land, count++, and union with each of the 4 land neighbors (each successful union decrements count).

Solution#

class Solution {
    vector<int> parent, rnk;
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
    bool unite(int a, int b) {
        a = find(a); b = find(b); if (a == b) return false;
        if (rnk[a] < rnk[b]) swap(a, b);
        parent[b] = a; if (rnk[a] == rnk[b]) ++rnk[a];
        return true;
    }
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        parent.assign(m * n, -1); rnk.assign(m * n, 0);
        vector<int> ans;
        ans.reserve(positions.size());
        int count = 0;
        static const int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
        for (auto& p : positions) {
            int r = p[0], c = p[1], u = r * n + c;
            if (parent[u] != -1) { ans.push_back(count); continue; }
            parent[u] = u;
            ++count;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int v = nr * n + nc;
                if (parent[v] != -1 && unite(u, v)) --count;
            }
            ans.push_back(count);
        }
        return ans;
    }
};

func numIslands2(m int, n int, positions [][]int) []int {
    parent := make([]int, m*n)
    rnk := make([]int, m*n)
    for i := range parent {
        parent[i] = -1
    }
    var find func(int) int
    find = func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
    unite := func(a, b int) bool {
        a, b = find(a), find(b)
        if a == b {
            return false
        }
        if rnk[a] < rnk[b] {
            a, b = b, a
        }
        parent[b] = a
        if rnk[a] == rnk[b] {
            rnk[a]++
        }
        return true
    }
    ans := make([]int, 0, len(positions))
    count := 0
    dr := []int{-1, 1, 0, 0}
    dc := []int{0, 0, -1, 1}
    for _, p := range positions {
        r, c := p[0], p[1]
        u := r*n + c
        if parent[u] != -1 {
            ans = append(ans, count)
            continue
        }
        parent[u] = u
        count++
        for k := 0; k < 4; k++ {
            nr, nc := r+dr[k], c+dc[k]
            if nr < 0 || nr >= m || nc < 0 || nc >= n {
                continue
            }
            v := nr*n + nc
            if parent[v] != -1 && unite(u, v) {
                count--
            }
        }
        ans = append(ans, count)
    }
    return ans
}

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        parent = [-1] * (m * n)
        rnk = [0] * (m * n)

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def unite(a: int, b: int) -> bool:
            a, b = find(a), find(b)
            if a == b:
                return False
            if rnk[a] < rnk[b]:
                a, b = b, a
            parent[b] = a
            if rnk[a] == rnk[b]:
                rnk[a] += 1
            return True

        ans = []
        count = 0
        dr = (-1, 1, 0, 0)
        dc = (0, 0, -1, 1)
        for r, c in positions:
            u = r * n + c
            if parent[u] != -1:
                ans.append(count)
                continue
            parent[u] = u
            count += 1
            for k in range(4):
                nr, nc = r + dr[k], c + dc[k]
                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    continue
                v = nr * n + nc
                if parent[v] != -1 and unite(u, v):
                    count -= 1
            ans.append(count)
        return ans

function numIslands2(m, n, positions) {
    const parent = new Array(m * n).fill(-1);
    const rnk = new Array(m * n).fill(0);
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    const unite = (a, b) => {
        a = find(a); b = find(b);
        if (a === b) return false;
        if (rnk[a] < rnk[b]) [a, b] = [b, a];
        parent[b] = a;
        if (rnk[a] === rnk[b]) rnk[a]++;
        return true;
    };
    const ans = [];
    let count = 0;
    const dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1];
    for (const [r, c] of positions) {
        const u = r * n + c;
        if (parent[u] !== -1) {
            ans.push(count);
            continue;
        }
        parent[u] = u;
        count++;
        for (let k = 0; k < 4; k++) {
            const nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            const v = nr * n + nc;
            if (parent[v] !== -1 && unite(u, v)) count--;
        }
        ans.push(count);
    }
    return ans;
}

class Solution {
    private int[] parent;
    private int[] rnk;

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        parent = new int[m * n];
        rnk = new int[m * n];
        Arrays.fill(parent, -1);
        List<Integer> ans = new ArrayList<>();
        int count = 0;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        for (int[] p : positions) {
            int r = p[0], c = p[1];
            int u = r * n + c;
            if (parent[u] != -1) {
                ans.add(count);
                continue;
            }
            parent[u] = u;
            count++;
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int v = nr * n + nc;
                if (parent[v] != -1 && unite(u, v)) count--;
            }
            ans.add(count);
        }
        return ans;
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private boolean unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (rnk[a] < rnk[b]) {
            int t = a; a = b; b = t;
        }
        parent[b] = a;
        if (rnk[a] == rnk[b]) rnk[a]++;
        return true;
    }
}

function numIslands2(m: number, n: number, positions: number[][]): number[] {
    const parent: number[] = new Array(m * n).fill(-1);
    const rnk: number[] = new Array(m * n).fill(0);
    const find = (x: number): number => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    const unite = (a: number, b: number): boolean => {
        a = find(a); b = find(b);
        if (a === b) return false;
        if (rnk[a] < rnk[b]) [a, b] = [b, a];
        parent[b] = a;
        if (rnk[a] === rnk[b]) rnk[a]++;
        return true;
    };
    const ans: number[] = [];
    let count = 0;
    const dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1];
    for (const [r, c] of positions) {
        const u = r * n + c;
        if (parent[u] !== -1) {
            ans.push(count);
            continue;
        }
        parent[u] = u;
        count++;
        for (let k = 0; k < 4; k++) {
            const nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            const v = nr * n + nc;
            if (parent[v] !== -1 && unite(u, v)) count--;
        }
        ans.push(count);
    }
    return ans;
}

Editorial#

DSU naturally fits streaming additions: each new cell increments the component count by one for itself, then unions decrement the count by one per successful merge. Using parent[u] = -1 as a “not land yet” marker avoids a separate boolean grid. The duplicate-position guard parent[u] != -1 ensures we don’t double-count.

Complexity#

Time: O(K * α(M * N)) for K positions.
Space: O(M * N).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#