The problem
There are n people, numbered 0 to n - 1, each in a group of their own. Pairs arrive one at a time; a pair (a, b) joins the group of a and the group of b into one. Return a list with one number per pair: the size of the largest group just after that pair.
largest_after_each(5, [(0, 1), (2, 3), (1, 2), (3, 4)])
# [2, 2, 4, 5]
A pair may join people who are already in one group, or a person with themselves; then 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
- Up to 200,000 people and 200,000 pairs. Looking through all the groups after each pair is too slow.
Builds on DSUF-2 Union by rank.
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 | Already together | Not run | |
| 3 | One element | Not run | |
| 4 | Small groups join | Not run | |
| 5 | No pairs | Not run | |
| 6 | Star | Not run | |
| 7 | 200,000 pairs | Not run | |
| 8 | A long chain | Not run |