Verify a Topological Order

1. Define the problem

You are given numNodes nodes labeled 0 to numNodes - 1, a list of directed edges, and a candidate order — a permutation of every node. Return true if order is a valid topological order of the graph, or false otherwise. An order is valid when it contains every node exactly once and, for every edge, the source node appears before the destination node in it. Record each node's position in order, then check every edge against those positions in a single pass.

Constraints

1 ≤ numNodes ≤ 1000
0 ≤ edges.length ≤ 1000
order.length == numNodes
edges_i.length == 2

Example

InputnumNodes = 4, edges = [[0,1],[0,2],[1,3],[2,3]], order = [0,1,2,3]

Outputtrue

Explanation Every edge points from an earlier position in order to a later one.

2. Know the words first

In plain terms

Topological order: A sequence of all the nodes in a directed graph where every edge points from an earlier node to a later one.
Position: A node's index within the candidate order — where it sits, from 0 (first) to numNodes - 1 (last).

3. Visualize the solution

Check every edge against each node's position in the order

Statusinit

order = [0,1,2,3]. Position built: 0→0, 1→1, 2→2, 3→3.

What happens in this step

order  = [0, 1, 2, 3]
position[0] = 0
position[1] = 1
position[2] = 2
position[3] = 3

Each node's position is just its index in order — this table records where every node sits so each edge can be checked in O(1) below.

Step 1 of 4

Steps to visualize

Build a position map: position_node = the node's index in the given order.
Reject immediately if the order is the wrong length or repeats a node.
For every edge (from, to), confirm position_from is less than position_to.
If any edge fails that check, the order is invalid — otherwise it is valid.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Check every edge against each node's position in the order

Statusinit

order = [0,1,2,3]. Position built: 0→0, 1→1, 2→2, 3→3.

What happens in this step

order  = [0, 1, 2, 3]
position[0] = 0
position[1] = 1
position[2] = 2
position[3] = 3

Each node's position is just its index in order — this table records where every node sits so each edge can be checked in O(1) below.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function isValidTopologicalOrder(numNodes, edges, order) {
  if (order.length !== numNodes) {
    return false;
  }

  const seen = new Set(order);
  if (seen.size !== numNodes) {
    return false;
  }
  for (const node of order) {
    if (node < 0 || node >= numNodes) {
      return false;
    }
  }

  const position = new Array(numNodes);
  for (let i = 0; i < order.length; i++) {
    position[order[i]] = i;
  }

  for (const [from, to] of edges) {
    if (position[from] >= position[to]) {
      return false;
    }
  }

  return true;
}

Time: O(numNodes + edges.length)
Space: O(numNodes)

6. Test cases

Test cases

Input	Expected	Covers
`numNodes = 4, edges = [[0,1],[0,2],[1,3],[2,3]], order = [0,1,2,3]`	`true`	example from the docstring
`numNodes = 4, edges = [[0,1],[0,2],[1,3],[2,3]], order = [0,2,1,3]`	`true`	a different but equally valid order for the same graph
`numNodes = 4, edges = [[0,1],[0,2],[1,3],[2,3]], order = [3,2,1,0]`	`false`	the exact reverse of a valid order fails immediately
`numNodes = 4, order = [0,1,2]`	`false`	order is missing a node, so its length does not match numNodes
`numNodes = 4, order = [0,1,1,3]`	`false`	order repeats a node instead of including every node once
`numNodes = 3, edges = [], order = [2,0,1]`	`true`	no edges at all, so every permutation is trivially valid
`numNodes = 1, edges = [], order = [0]`	`true`	smallest valid input, a single node with no edges
`numNodes = 3, edges = [[0,1],[1,2]], order = [0,2,1]`	`false`	one edge in the middle of the order is violated even though the first passes

Verify a Topological Order