Staff
Number of Islands II
You are given an initially empty m x n 2D grid grid, where every cell is water.
An island is a group of land cells connected horizontally or vertically. You are also given an array positions, where positions[i] = [r_i, c_i] represents the operation of changing the cell at row r_i and column c_i from water to land.
After each operation, return the number of islands in the grid. If an operation adds land to a cell that is already land, the grid does not change, but you should still record the current number of islands.
Return an array answer where answer[i] is the number of islands after applying positions[i].
Your solution should process the updates efficiently; recomputing all islands from scratch after every operation is too slow.
Example 1
Input
m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]Output
[1,1,2,3]After the four additions, the island counts are 1, 1, 2, and 3 respectively.
Example 2
Input
m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[1,2]]Output
[1,1,2,2]The second addition connects to the first land cell, and the duplicate fourth addition does not change the island count.
Constraints
- 1 <= m, n <= 10^4
- 1 <= m * n <= 10^4
- 1 <= positions.length <= 10^4
- positions[i].length == 2
- 0 <= positions[i][0] < m
- 0 <= positions[i][1] < n