Number of Islands II
Difficulty: Hard
Category: DSA
Topics: Array, Hash Table, Union Find
Asked at: Amazon
You are given two integers `m` and `n` representing the number of rows and columns of a 2D grid, initially filled with water (`0`). You are also given a list of positions `positions`, where each `positions[i] = [ri, ci]` represents adding a land cell (`1`) at position `(ri, ci)` in the grid.
An **island** is a group of connected land cells (horizontally or vertically adjacent). After each addition of land, you must determine the current number of islands in the grid.
Return a list of integers representing the number of islands after each operation in `positions`.
**Constraints:**
- `1 <= m, n <= 10^4`
- `0 <= positions.length <= min(m * n, 10^4)`
- `positions[i].length == 2`
- `0 <= ri < m`, `0 <= ci < n`
- No position is repeated in `positions`
You should return a list of length `positions.length`, where the `i`-th element is the number of islands after adding land at `positions[i]`.