Mother Vertex in a Directed Graph
Updated
Problem statement
A directed graph has n vertices labeled from 0 to n - 1. Each edges[i] = [u, v] is a one-way edge from vertex u to vertex v.
A mother vertex is a vertex from which you can reach every vertex of the graph by following edges in their direction. A vertex always counts as reaching itself.
Return the smallest label of a mother vertex. If the graph has no mother vertex, return -1.
Function
findMotherVertex(n: int, edges: int[][]) → intExamples
Example 1
n = 6edges = [[3,1],[1,0],[0,2],[3,4],[4,3],[2,5]]return = 3From vertex 3 the path 3 → 1 → 0 → 2 → 5 reaches vertices 1, 0, 2 and 5, and the edge 3 → 4 reaches vertex 4. So 3 is a mother vertex. Vertex 4 is one too, because 4 → 3 leads to everything else, but 3 is smaller. Vertices 0, 1, 2 and 5 cannot reach vertex 3.
Example 2
n = 4edges = [[0,1],[2,1],[1,3]]return = -1No edge goes into vertex 0 or vertex 2, so each of them can only be reached from itself. No single vertex reaches both, so there is no mother vertex.
Example 3
n = 1edges = []return = 0The graph has one vertex and no edges. Vertex 0 reaches itself, which is every vertex, so the answer is 0.
Constraints
1 <= n <= 10^40 <= edges.length <= 2 * 10^4edges[i].length == 20 <= edges[i][0], edges[i][1] <= n - 1- The same edge may appear more than once, and an edge may go from a vertex to itself.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Number of IslandsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Course SchedulePlaud · ONSITE INTERVIEW
- Course Schedule Cycle DetectionGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
- Validate and Resolve Evaluation ChainsPlaid · PHONE SCREEN · ONSITE INTERVIEWPlaid interview questions
- Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Audit Discounted Category AncestorsFaire · ONSITE INTERVIEW
- Evaluate DivisionPhonePe · ONSITE INTERVIEWPhonePe interview questions
- Count Friend CirclesOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions