Lowest Common Manager
MediumTrees · Google · Atlassian
pairs lists [manager, report] for every reporting line in a company; exactly one person has no manager. A person's team is themself and everyone who reports to them directly or indirectly.
Return the name of the deepest person whose team contains every employee in names. names may repeat a name, and the answer can be one of the listed employees.
Example 1
- Input:
- pairs = [["Omar", "Tess"], ["Mia", "Lena"], ["Ravi", "Wes"], ["Mia", "Omar"], ["Lena", "Kofi"], ["Omar", "Ravi"], ["Ravi", "Uma"]], names = ["Uma", "Tess"]
- Output:
- "Omar"
- Explanation
- Omar's team holds both Uma and Tess, while Ravi's team has Uma but not Tess.
Example 2
- Input:
- pairs = [["Omar", "Tess"], ["Mia", "Lena"], ["Ravi", "Wes"], ["Mia", "Omar"], ["Lena", "Kofi"], ["Omar", "Ravi"], ["Ravi", "Uma"]], names = ["Ravi", "Wes"]
- Output:
- "Ravi"
Example 3
- Input:
- pairs = [["Omar", "Tess"], ["Mia", "Lena"], ["Ravi", "Wes"], ["Mia", "Omar"], ["Lena", "Kofi"], ["Omar", "Ravi"], ["Ravi", "Uma"]], names = ["Uma", "Uma", "Kofi"]
- Output:
- "Mia"
Constraints
1 <= pairs.length <= 10^5- Names are distinct non-empty strings, and
pairsforms a single tree 1 <= names.length <= 10^5, and every name innamesappears inpairs- The reporting chain can be up to
pairs.lengthpeople deep