FastPrepLexicographically Smallest Topological Order

Lexicographically Smallest Topological Order

Intuit logoIntuit● MediumINTERNOA
Learn

Problem statement

Find a topological order of a directed graph. For this exercise, assume its vertices are numbered 0 through n-1, including vertices that do not appear in any edge. Each pair [source,destination] in edges requires source to appear before destination.

For this exercise, assume repeated identical pairs represent one dependency. Return every vertex exactly once in the lexicographically smallest valid order: at the first differing position, the smaller vertex label wins.

For this exercise, assume a self-loop or any directed cycle makes a complete order impossible; return an empty array in that case. An empty graph also returns an empty array. Do not return a partial order or modify edges.

Function

topologicalOrder(n: int, edges: int[][]) → int[]

Examples

Example 1

n = 4edges = [[0,2],[1,2],[2,3]]return = [0,1,2,3]

Initially 0 and 1 are available. Choosing the smaller label first gives [0,1,2,3].

Example 2

n = 3edges = [[0,1],[1,0]]return = []

The directed cycle prevents a complete topological order even though isolated vertex 2 is available; return an empty array.

Example 3

n = 4edges = [[2,1]]return = [0,2,1,3]

Vertices 0, 2 and 3 are initially free. After 0 then 2, vertex 1 becomes free and precedes 3, giving [0,2,1,3].

Constraints

  • For this exercise, assume 0 <= n <= 200 and 0 <= edges.length <= 500.
  • Every edge has exactly two integers in [0,n-1]; when n=0, the edge list is empty.
  • Duplicate pairs and self-loops are allowed.

More Intuit problems

See Intuit hiring insights
public int[] topologicalOrder(int n, int[][] edges) {
    // Write your code here.
    return new int[0];
}
n4
edges[[0,2],[1,2],[2,3]]
expected[0,1,2,3]
Checking account…