forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0721-accounts-merge.kt
62 lines (51 loc) · 1.49 KB
/
0721-accounts-merge.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class DSU(val n: Int) {
val parent = IntArray(n) {it}
val rank = IntArray(n) {1}
fun find(x: Int): Int {
if (x != parent[x])
parent[x] = find(parent[x])
return parent[x]
}
fun union(x: Int, y: Int): Boolean {
val pX = find(x)
val pY = find(y)
if(pX == pY)
return false
if (rank[pX] > rank[pY]) {
parent[pY] = pX
rank[pX] += rank[pY]
} else {
parent[pX] = pY
rank[pY] += rank[pX]
}
return true
}
}
class Solution {
fun accountsMerge(accounts: List<List<String>>): List<List<String>> {
val uf = DSU(accounts.size)
val emailToAcc = HashMap<String, Int>()
for ((i,accs) in accounts.withIndex()) {
for (j in 1..accs.lastIndex) {
val e = accs[j]
if (e in emailToAcc.keys) {
uf.union(i, emailToAcc[e]!!)
} else {
emailToAcc[e] = i
}
}
}
val emails = hashMapOf<Int, ArrayList<String>>()
for ((e, i) in emailToAcc) {
val main = uf.find(i)
emails[main] = emails.getOrDefault(main, ArrayList<String>()).apply { this.add(e) }
}
val res = ArrayList<ArrayList<String>>()
for ((i, em) in emails.entries) {
em.sort()
em.add(0, accounts[i][0])
res.add(em)
}
return res
}
}