An m x n grid starts as all water. You are given positions, a list of [row, col] cells that turn into land one at a time, in order. After each position is added, report the number of islands. An island is a group of land cells connected horizontally or vertically.
- A
DSU class with find(x), union(a, b) (returns false when they were already together), setSize(x) and a components counter is already provided - A position may repeat; a repeated position changes nothing and repeats the previous count
- Return an array with one number per position
- A grid with
m * n up to 10^5 and as many positions: rescanning the grid after every position is too slow