Loading page…
Practice problem · easy
You work on a payments app. There are n wallets, numbered 0 to n - 1. Two wallets are linked when the same device logged in to both of them. The review team wants to look at the biggest cluster of linked wallets first.
A cluster is a group of wallets joined by a chain of links, long or short. A wallet with no link is a cluster of one. Your team lead says: "How many wallets are in the biggest cluster?"
Write largest_group(n, links).
n is the number of wallets.links[i] = [a, b] means one device logged in to both wallet a and wallet b.The same pair can be listed more than once.
Input: n = 7, links = [[0, 1], [1, 2], [3, 4], [5, 6], [4, 6]]
Output: 4Keep each cluster with its size. Start with 7 clusters of size 1. Each link between two different clusters merges them, and the new size is the sum.
| Link | Clusters merged | Sizes | Largest so far |
|---|---|---|---|
| start | seven clusters of 1 | 1 | |
| [0, 1] | {0} and {1} | {0, 1}: 2 | 2 |
| [1, 2] | {0, 1} and {2} | {0, 1, 2}: 3 | 3 |
| [3, 4] | {3} and {4} | {3, 4}: 2 | 3 |
| [5, 6] | {5} and {6} | {5, 6}: 2 | 3 |
| [4, 6] | {3, 4} and {5, 6} | {3, 4, 5, 6}: 4 | 4 |
The clusters are {0, 1, 2} and {3, 4, 5, 6}. The largest has 4 wallets.
Input: n = 3, links = []
Output: 1With no links, every wallet is a cluster of one. The largest has 1 wallet.
Input: n = 4, links = [[0, 1], [2, 3], [1, 2]]
Output: 4The third link joins {0, 1} and {2, 3}: one cluster of 4 wallets.
1 ≤ n ≤ 100,0000 ≤ len(links) ≤ 200,000, and every row is [a, b] with 0 ≤ a, b < n and a ≠ bThere can be 100,000 wallets and 200,000 links. Renaming a whole cluster for every link costs up to n each, so m links cost m × n: 20 billion steps. Union-find merges two clusters in nearly constant time and already keeps each cluster's size.
largest_group · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.