Understanding the Problem
We are given a 2D grid of size n x m
, where initially all cells are water. Over time, land is added to the grid at specific coordinates through a series of queries. Our goal is to report the number of islands after each land addition.
An island is a group of connected land cells (connected horizontally or vertically). As land is added, some cells may connect to form a larger island, or they may remain isolated.
The challenge lies in efficiently updating and keeping track of the number of islands after each addition, especially as the number of queries can be large.
Step-by-Step Solution with Example
step 1: Flatten the 2D Grid
To simplify union-find operations, we treat the 2D grid as a 1D array. Each cell can be represented as cell_id = row * m + col
. This gives a unique index to each cell in the grid.
step 2: Initialize DSU
We create a Disjoint Set Union (DSU) structure, also known as Union-Find, to group connected land cells. Initially, all cells are water, so they are not part of any set.
step 3: Process Each Query
For each land addition query:
- Convert the 2D coordinates to a 1D cell index.
- If the cell is already land, skip it (no changes).
- Otherwise, mark the cell as land and increment the island count.
- Check its 4 neighbors (up, down, left, right). If a neighbor is land and belongs to a different set, merge the sets using
union()
. For each merge, decrease the island count by 1 since two separate islands became one.
step 4: Return Island Count After Each Query
After processing each query, record the current island count in the result list.
Example:
Let’s say n = 3
, m = 3
and the queries are: [(0,0), (0,1), (1,2), (2,1), (1,1)]
.
- Add (0,0): New land. Count = 1.
- Add (0,1): New land. It's adjacent to (0,0), so union them. Count = 1.
- Add (1,2): New isolated land. Count = 2.
- Add (2,1): New isolated land. Count = 3.
- Add (1,1): New land. It's adjacent to (0,1), (1,2), and (2,1). All three are in different sets. Union with all. Count goes from 4 → 3 → 2 → 1.
Edge Cases
- Adding land to an already land cell: Should be skipped, no effect on count.
- Adjacent lands already connected: Union will detect they’re in the same set; no change to count.
- Land added at the borders: Ensure neighbor checks do not go out of bounds.
Finally
This problem is a perfect use case for Disjoint Set Union (DSU). It efficiently maintains groups of connected land cells and helps track how the number of islands evolves over time.
Using optimizations like path compression and union by rank, we can process each query in nearly constant time, making this approach scalable even for large grids and many queries.
Comments
Loading comments...