Interview 150
Accounts Merge
- Problem
- LC 721
- File
- interview150_LC721AccountsMerge.java
- Path
- pkg5leetcode/interview150/interview150_LC721AccountsMerge.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC721AccountsMerge.java
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/** LC 721 Accounts Merge */4import java.util.*;5 6public class interview150_LC721AccountsMerge {7 static int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }8 9 static List<List<String>> accountsMerge(List<List<String>> accounts) {10 Map<String,Integer> id = new HashMap<>();11 Map<String,String> name = new HashMap<>();12 int n = 0;13 for (List<String> acc : accounts) {14 for (int i = 1; i < acc.size(); i++) {15 id.putIfAbsent(acc.get(i), n++);16 name.putIfAbsent(acc.get(i), acc.get(0));17 }18 }19 int[] p = new int[n]; for (int i = 0; i < n; i++) p[i] = i;20 for (List<String> acc : accounts) {21 int first = id.get(acc.get(1));22 for (int i = 2; i < acc.size(); i++) { int j = id.get(acc.get(i)); p[find(p, first)] = find(p, j); }23 }24 Map<Integer, TreeSet<String>> groups = new HashMap<>();25 for (var e : id.entrySet()) groups.computeIfAbsent(find(p, e.getValue()), k -> new TreeSet<>()).add(e.getKey());26 List<List<String>> res = new ArrayList<>();27 for (var g : groups.values()) {28 List<String> row = new ArrayList<>(g);29 row.add(0, name.get(row.get(0)));30 res.add(row);31 }32 return res;33 }34 35 public static void main(String[] args) {36 System.out.println(accountsMerge(List.of(37 List.of("John","johnsmith@mail.com","john_newyork@mail.com"),38 List.of("John","johnsmith@mail.com","john00@mail.com"),39 List.of("Mary","mary@mail.com"))));40 }41}