778. Islands Appearing
A volcanic ocean is mapped as a grid with m rows and n columns that is initially all water. The entry positions[k] = [r, c] says that at step k the cell in row r and column c rises out of the sea and becomes land (rows and columns are 0-indexed). An island is a maximal set of land cells connected through shared edges (up, down, left, right); diagonal contact does not connect cells.
Return an array of the same length as positions whose entry k is the number of islands after the first k + 1 cells have become land. A position may be listed more than once; raising a cell that is already land changes nothing.
Example 1
- Input:
- m = 3n = 3positions = [[0,0],[2,2],[0,2],[1,2],[0,1]]
- Output:
- [1,2,3,2,1]
- Explanation:
Land appears at (0,0), (2,2), (0,2): three islands. Then (1,2) joins (0,2) and (2,2), leaving two; finally (0,1) joins (0,0) with the big island, leaving one.
Example 2
- Input:
- m = 2, n = 2, positions = [[0,0],[0,0],[1,1],[0,1]]
- Output:
- [1,1,2,1]
- Explanation:
The repeated position changes nothing; (1,1) is a second island; (0,1) touches both (0,0) and (1,1), merging everything into one.
Example 3
- Input:
- m = 1n = 5positions = [[0,0],[0,4],[0,2],[0,1],[0,3]]
- Output:
- [1,2,3,2,1]
- Explanation:
In a single row the islands at columns 0, 4 and 2 are separate; adding column 1 merges 0 with 2, and adding column 3 merges the rest.
Constraints
- 1 ≤ m, n and m * n ≤ 106
- 0 ≤ positions.length ≤ 105
- 0 ≤ r < m and 0 ≤ c < n for every position
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O((m*n + k) * alpha(m*n))
- Space
- O(m*n)