Count Islands in a Grid and Track the Count as Land Cells Are Added
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A map is a grid with `m` rows and `n` columns in which every cell is land (`1`) or water (`0`). An island is a maximal group of land cells connected horizontally or vertically. Cells that touch only at a corner are not connected.
You are given the initial map and a sequence of additions, each of which turns one cell into land. Report the number of islands before any addition, and again after each addition.
### Function Signature
```python
def island_counts(grid: list[list[int]], additions: list[tuple[int, int]]) -> list[int]:
```
### Rules
- `grid[r][c]` is `1` for land and `0` for water, where `r` is the row index and `c` is the column index.
- An addition `(r, c)` turns cell `(r, c)` into land. If that cell is already land, either initially or because of an earlier addition, the map does not change.
- Additions are applied in the given order. Land never turns back into water.
- Return a list of length `len(additions) + 1`. Element `0` is the number of islands in the initial grid. For `i >= 1`, element `i` is the number of islands after the first `i` additions have been applied.
### Constraints
- `1 <= m <= 1000`, `1 <= n <= 1000` and `m * n <= 200000`
- Every row of `grid` has exactly `n` entries, each `0` or `1`.
- `0 <= len(additions) <= 200000`
- Every addition `(r, c)` satisfies `0 <= r < m` and `0 <= c < n`. The same cell may appear more than once.
- Every count is at most `m * n`, so all values fit in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: grid = [[1, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 1]], additions = []
Output: [3]
```
The islands are {(0, 0), (0, 1)}, {(1, 3), (2, 3)} and {(2, 0)}. With no additions, the only element is the initial count.
**Example 2**
```text
Input: grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]], additions = [(0, 0), (0, 1), (1, 2), (2, 1), (1, 1), (1, 1)]
Output: [0, 1, 1, 2, 3, 1, 1]
```
The grid starts with no land. (0, 0) creates an island and (0, 1) joins it. (1, 2) and (2, 1) each touch no land, so each creates a new island. (1, 1) touches all three islands and merges them into one. The second (1, 1) is already land, so nothing changes.
**Example 3**
```text
Input: grid = [[1, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 1]], additions = [(0, 2), (0, 3), (1, 0)]
Output: [3, 3, 2, 1]
```
(0, 2) joins the top-left island. It touches (1, 3) only at a corner, so the count stays 3. (0, 3) connects the top-left island to the island at (1, 3) and (2, 3), giving 2. (1, 0) connects the merged island to (2, 0), giving 1.
Overview: Count the islands of horizontally or vertically connected land cells in a grid, then report the updated count after each cell in a sequence is turned into land. Tests grid connectivity, handling a new cell that merges several islands at once, and processing up to 200,000 additions efficiently.
A map is a grid with m rows and n columns in which every cell is land (1) or water (0). An island is a maximal group of land cells connected horizontally or vertically. Cells that touch only at a corner are not connected.
You are given the initial map grid and a sequence of additions, each of which turns one cell into land. Each addition is given as a pair [r, c]. Report the number of islands before any addition, and again after each addition.
Rules:
- grid[r][c] is 1 for land and 0 for water, where r is the row index and c is the column index.
- An addition [r, c] turns cell (r, c) into land. If that cell is already land, either initially or because of an earlier addition, the map does not change.
- Additions are applied in the given order. Land never turns back into water.
- Return a list of length len(additions) + 1. Element 0 is the number of islands in the initial grid. For i >= 1, element i is the number of islands after the first i additions have been applied.
Constraints:
- 1 <= m <= 1000, 1 <= n <= 1000 and m * n <= 200000
- Every row of grid has exactly n entries, each 0 or 1.
- 0 <= len(additions) <= 200000
- Every addition [r, c] satisfies 0 <= r < m and 0 <= c < n. The same cell may appear more than once.
- Every count is at most m * n, so all values fit in a 32-bit signed integer (no value can exceed 2^31 - 1).
Example 1:
Input: grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]], additions = [[0, 0], [0, 1], [1, 2], [2, 1], [1, 1], [1, 1]]
Output: [0, 1, 1, 2, 3, 1, 1]
The grid starts with no land. [0, 0] creates an island and [0, 1] joins it. [1, 2] and [2, 1] each touch no land, so each creates a new island. [1, 1] touches all three islands and merges them into one. The second [1, 1] is already land, so nothing changes.
Example 2:
Input: grid = [[1, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 1]], additions = [[0, 2], [0, 3], [1, 0]]
Output: [3, 3, 2, 1]
The initial islands are {(0, 0), (0, 1)}, {(1, 3), (2, 3)} and {(2, 0)}. [0, 2] joins the top-left island; it touches (1, 3) only at a corner, so the count stays 3. [0, 3] connects the top-left island to the island at (1, 3) and (2, 3), giving 2. [1, 0] connects the merged island to (2, 0), giving 1.
Constraints
- 1 <= m <= 1000, 1 <= n <= 1000 and m * n <= 200000
- Every row of grid has exactly n entries, each 0 or 1.
- 0 <= len(additions) <= 200000
- Every addition [r, c] satisfies 0 <= r < m and 0 <= c < n. The same cell may appear more than once.
- Every count is at most m * n, so all values fit in a 32-bit signed integer (no value can exceed 2^31 - 1).
Examples
Input: ([[1, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 1]], [])
Expected Output: [3]
Explanation: Source example 1: islands {(0,0),(0,1)}, {(1,3),(2,3)}, {(2,0)} and no additions, so only the initial count is returned.
Input: ([[0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0], [0, 1], [1, 2], [2, 1], [1, 1], [1, 1]])
Expected Output: [0, 1, 1, 2, 3, 1, 1]
Explanation: Source example 2: islands are created, (1,1) merges three islands into one, and its repeat changes nothing.
Hints
- Land never turns back into water, so adding one cell can only change the island count in a limited way; consider what the new cell can connect to.
- If the new cell touches the same island from more than one side, that island must only be counted as merged once, so you need a fast way to tell whether two land cells already belong to the same island.
- Recounting all islands from scratch after every addition is too slow with up to 200000 cells and 200000 additions.
Community answers
Answer by Cybot
most asked
Answer by Cybot
this was asked recently
Answer by Denys
I was asked a similar question a few years ago. I solved it using Disjoint Union with path compression but I also was asked to estimate its time complexity.
Answer by Coderka14
#include
using namespace std;
class DSU
{
private:
vector parent;
vector sz;
public:
DSU(int n)
{
parent.resize(n);
sz.assign(n, 1);
for (int i = 0; i < n; i++)
{
parent[i] = i;
}
}
int find(int x)
{
if (parent[x] == x)
{
return x;
}
return parent[x] = find(parent[x]);
}
// Returns true only if two different components merge.
bool unite(int x, int y)
{
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY)
{
return false;
}
// Union by size
if (sz[rootX] < sz[rootY])
{
swap(rootX, rootY);
}
parent[rootY] = rootX;
sz[rootX] += sz[rootY];
return true;
}
};
class Solution
{
public:
vector island_counts( vector>& grid, vector>& additions)
{
int m = grid.size();
int n = grid[0].size();
DSU dsu(m * n);
// Up, down, left, right
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
auto id = &
{
return r * n + c;
};
int islands = 0;
// Step 1: Build DSU for the initial grid.
for (int r = 0; r < m; r++)
{
for (int c = 0; c < n; c++)
{
if (grid[r][c] == 1)
{
// Initially, every land cell is an island.
islands++;
// Check only right and down to avoid
// processing each initial edge twice.
if (r + 1 < m && grid[r + 1][c] == 1)
{
if (dsu.unite(id(r, c), id(r + 1, c)))
{
islands--;
}
}
if (c + 1 < n && grid[r][c + 1] == 1)
{
if (dsu.unite(id(r, c), id(r, c + 1)))
{
islands--;
}
}
}
}
}
vector answer;
answer.push_back(islands);
// Step 2: Process each addition.
for (auto& cell : additions)
{
int r = cell[0];
int c = cell[1];
// Duplicate addition: nothing changes.
if (grid[r][c] == 1