Number of islands as land is added
A grid starts as all water. Positions are turned into land one at a time; after each addition, return the current number of islands (land cells connected up, down, left or right). Use union-find so each addition is nearly constant time.
No answer yet. Write the first one; the best answer gets endorsed.