Q34 Accounts Merge - LeetCode 721
Mon Jun 12 2023 09:20:45 GMT+0000 (Coordinated Universal Time)
Saved by @Ayush_dabas07
class Solution { int parent[] = new int[10001]; //maximum constraints public List<List<String>> accountsMerge(List<List<String>> accounts) { /* Q34 graph playlist , DSU concept*/ //initializing parent array for(int i = 0 ;i < 10001 ; i++) parent[i] = i; //making a HM< email , uid> so that we can group them HashMap<String , Integer> euid = new HashMap<>(); //HM to get email -> name HashMap<String ,String > etn = new HashMap<>(); int uid = 0; //grouping emails and updating hashmaps for(List<String> account : accounts){ String name = " "; for(String email : account){ //store name if 1st time if(name == " "){ name = email; continue; } //update HM if(euid.containsKey(email) == false){ euid.put(email , uid); uid++; } if(etn.containsKey(email) == false){ etn.put(email , name); } //finding parents based on euid and merging with 1st email of that group int uid_p1 = euid.get(account.get(1)); int uid_p2 = euid.get(email); int p1 = findparent(uid_p1); int p2 = findparent(uid_p2); if(p1 != p2) parent[p2] = p1; } } //grouping parents and emails in HashMap HashMap<Integer , List<String>> pte = new HashMap<>(); for(String email : etn.keySet()){ //finding uid of email int unique_id = euid.get(email); //finding parent int par = findparent(unique_id); pte.computeIfAbsent(par , k-> new ArrayList<>()).add(email); } List<List<String>> ans = new ArrayList<>(); //making final answer for(List<String> emails : pte.values()){ //finding name against which email will be added String name = etn.get(emails.get(0)); //sorting emails in ascending order Collections.sort(emails); //adding into answer List<String> temp = new ArrayList<>(); //adding name first temp.add(name); //adding emails for(String email : emails) temp.add(email); ans.add(temp); } return ans; } public int findparent(int u){ if(parent[u] == u) return parent[u]; int temp = findparent(parent[u]); parent[u] = temp; return temp; } }
Comments