Synonym Groups
Given a list of string pairs, each meaning the two words are synonyms — a relation that is bidirectional and transitive — merge all related words into groups. Return a map whose key is the lexicographically smallest word in each group and whose value is the group sorted ascending.
synonymGroups([["a", "b"], ["b", "c"], ["d", "e"]])
-> { "a": ["a", "b", "c"], "d": ["d", "e"] }Pairs may repeat, may arrive in any order, and a word may be paired with itself — it still forms a group. Comparison is plain string order ("Mango" sorts before "apple").
Hints
Hint 1
Restate the relation as connected components of an undirected graph. Union-find fits because the relation is incremental: register both words, union them, then group every word by its root.
Hint 2
DFS over an adjacency list also works and is easier to write; offer both and let the interviewer pick. Either way, sort each group and key it by its first element.