Show problems as
Classic problem #305HardArrayHash TableUnion-Find

Number of Islands II

Real-world version: Reclaimed Flats After Each Dump
Tracked in this browser only
Read Number of Islands II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey crew is reclaiming a shallow tidal basin drawn as an m x n grid of cells. Every cell is open water on day zero.

You are handed positions, and positions[k] = [r, c] names the single cell that the barge packs with gravel on day k, which makes that cell dry. Should the crew pick a cell that is already dry, nothing about the basin changes that day.

Call two dry cells part of the same flat when they meet along a shared horizontal or vertical edge. Cells that only touch at a corner stay in separate flats.

Return answer, a list as long as positions, in which answer[k] records how many separate flats the basin holds once day k's load of gravel has been placed.

Examples

Example 1

Input
m = 2, n = 4, positions = [[0,1],[1,3],[0,3],[0,2]]
Output
[1,2,2,1]

Day 0 leaves the single dry cell (0,1). Day 1 dries (1,3), which touches nothing dry, so there are two flats. Day 2 dries (0,3), which shares an edge with (1,3), keeping the total at two. Day 3 dries (0,2), which shares edges with both (0,1) and (0,3), so every dry cell now sits in one flat.

Example 2

Input
m = 1, n = 5, positions = [[0,4],[0,2],[0,0],[0,3]]
Output
[1,2,3,2]

The first three days dry three cells that are pairwise non-adjacent, giving counts 1, 2 and 3. Day 3 dries (0,3), which shares edges with (0,2) and (0,4), leaving the flats {(0,0)} and {(0,2),(0,3),(0,4)}.

Example 3

Input
m = 3, n = 3, positions = [[1,1],[1,1],[2,1],[0,1]]
Output
[1,1,1,1]

Day 1 repeats cell (1,1), which is already dry, so the basin is unchanged and the count stays at 1. Days 2 and 3 each dry a cell sharing an edge with (1,1).

Example 4

Input
m = 2, n = 2, positions = [[0,0],[1,1],[0,1]]
Output
[1,2,1]

After day 1 the dry cells (0,0) and (1,1) touch only at a corner, so they are two flats. Day 2 dries (0,1), which shares an edge with each of them, so the count falls to one.

Constraints

  • 1 <= m, n, positions.length <= 10^4
  • 1 <= m * n <= 10^4
  • positions[k].length == 2
  • 0 <= positions[k][0] < m
  • 0 <= positions[k][1] < n

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def num_islands2(m: int, n: int, positions: list[list[int]]) -> list[int]:
Java
public List<Integer> numIslands2(int m, int n, int[][] positions)

More on the same topics