A large company directory shows, for any two people, their closest shared manager. There are n people numbered 0 to n - 1. managers[i] is the direct manager of person i, or -1 for the one person at the top. People are not listed in any particular order.
Write commonManagers(managers, queries) where each query is [a, b]. For each query, return the lowest common ancestor of a and b: the deepest person who is a or above a, and also b or above b. If a manages b (directly or not), the answer is a. Aim for about O(log n) per query.
Input: managers = [-1,0,0,1,1,2,2], queries = [[3,4],[3,6],[5,2]] Output: [1,0,2]
3 and 4 both report to 1. 3 and 6 only meet at 0. 2 manages 5.
Input: managers = [-1,0], queries = [[1,1],[0,1]] Output: [1,0]
A person is their own common manager with themself.
1 <= n <= 5 * 10^41 <= queries.length <= 5 * 10^4Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #374 Common Manager Queries for an Org Chart. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.