Accounts Merge LeetCode solution in C++

1
// if you like this, please give me a upvote
2
class Solution {
3
 public:
4
  int parents[1001]; // why 1001? becoz it is max length of accounts, see
5
                     // constraints (1 <= accounts.length <= 1000)
6

7
  // function to find original parent
8
  int findpar(int parents[], int to_find) {
9
    while (parents[to_find] != to_find) to_find = parents[to_find];
10

11
    return to_find;
12
  }
13

14
  vector<vector<string>> accountsMerge(vector<vector<string>> &accounts) {
15
    // Link each email to their respective orginal parent,
16
    // we will do it by linking each email to its unique id
17
    unordered_map<string, int> email_to_id;
18

19
    for (int i = 0; i < accounts.size(); i++) // traversing from each row
20
    {
21
      parents[i] = i; // intially we don't know anything, so every parent is
22
                      // unique id of itself
23

24
      // why we start from 1? becoz emails starting from this place
25
      for (int j = 1; j < accounts[i].size(); j++) {
26
        // we check if this particular email already got their unique id, if yes
27
        // then we link it to its original parent unique id
28
        if (email_to_id.find(accounts[i][j]) != email_to_id.end()) {
29
          int parent1 = findpar(parents, i);
30
          int parent2 = findpar(parents, email_to_id[accounts[i][j]]);
31

32
          parents[parent1] = parent2;
33
        } else // if not find, then just give it to exsiting parent
34
        {
35
          email_to_id[accounts[i][j]] = parents[i];
36
        }
37
      }
38
    }
39

40
    // Now, we create a map that store all email id with their unique ids
41
    //            id,  vector of all emails
42
    unordered_map<int, vector<string>> resultant_map;
43

44
    for (auto it : email_to_id) {
45
      int uniq_id = findpar(parents, it.second);
46
      resultant_map[uniq_id].push_back(it.first);
47
    }
48

49
    // uff tired, so now towards final ans
50
    vector<vector<string>> ans;
51
    for (auto it : resultant_map) {
52
      vector<string> email = it.second;
53

54
      // question demand in sorted order
55
      sort(email.begin(), email.end());
56

57
      // inserting name in starting with the help of unique id
58
      email.insert(email.begin(), accounts[it.first][0]);
59

60
      ans.push_back(email);
61
    }
62
    return ans;
63
  }
64
};