The problem
A map has rows rows and cols columns, and starts as all water. One by one, the cells in cells rise and become land. Land cells that share a side (up, down, left or right) belong to the same island; touching at a corner does not count. Return the number of islands after each cell rises.
islands_after_each(3, 3, [(0, 0), (0, 1), (1, 2), (2, 1), (1, 1)])
# [1, 1, 2, 3, 1]
A cell may appear more than once; if it is already land, nothing changes.
Some tests join long chains. Write find with a loop, or make sure your trees stay short (lessons 2 and 3): a recursive find on a path of 100,000 nodes stops with RecursionError.
Limits
- The map has up to 100,000 cells, and up to 100,000 cells rise. Counting the islands from scratch after each one is too slow.
Builds on DSUF-5 Applications.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Corners do not touch | Not run | |
| 3 | Already land | Not run | |
| 4 | Edges of the map | Not run | |
| 5 | Wrapping rows | Not run | |
| 6 | A ring | Not run | |
| 7 | 300 by 300 | Not run | |
| 8 | A long snake | Not run |