Quick Overview

Return the lexicographically smallest valid ordering of a directed dependency graph, or an empty result when a cycle exists. The problem tests deterministic graph processing, duplicate-edge handling, isolated nodes, and rigorous complexity analysis.

Return the Lexicographically Smallest Topological Order

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Return the Lexicographically Smallest Topological Order ### Problem Implement `topologicalOrder(nodeCount, edges) -> order`. The directed graph contains nodes `0` through `nodeCount - 1`. Each edge `[from, to]` requires `from` to appear before `to`. Return the lexicographically smallest valid topological ordering: at the first index where two valid orders differ, choose the order with the smaller node ID. Return an empty integer array if the graph contains a directed cycle. When `nodeCount == 0`, the valid result is also an empty array. ### Portable Contract - `0 <= nodeCount <= 12,000`. - `edges` is a JSON array of two-integer arrays `[from, to]`, with `0 <= edges.length <= 20,000`. - Every endpoint satisfies `0 <= endpoint < nodeCount`. - Duplicate edges are allowed and represent the same precedence constraint; processing them repeatedly must not change the answer. - Self-loops are cycles. - Isolated nodes must appear in the returned order. - Do not modify `edges`. - Let `B` be the compact UTF-8 JSON byte length of `[nodeCount,edges]`, counting every bracket, comma, and digit. Inputs satisfy `B <= 160,000`. - Let `R` be the compact UTF-8 JSON byte length of the returned integer array. Inputs guarantee `R <= 80,000`, so the serialized input plus result is at most `240,000` bytes. - Target `O((nodeCount + edges.length) log nodeCount)` time and `O(nodeCount + edges.length)` auxiliary space, or better. All four languages use only integers and homogeneous integer arrays: `list[list[int]]` and `list[int]` in Python, arrays in JavaScript, `List<List<Integer>>` and `List<Integer>` in Java, and `vector<vector<int>>` and `vector<int>` in C++. ```hint Make the next choice canonical At each output position, consider all nodes whose prerequisites have already been satisfied and choose with the required tie-breaker. ``` ```hint Use the output length as evidence If no eligible node remains before every node is emitted, the unfinished nodes contain or depend on a cycle. ``` ### Examples ```text nodeCount = 4 edges = [[0, 2], [1, 2], [1, 3]] order = [0, 1, 2, 3] ``` ```text nodeCount = 3 edges = [[0, 1], [1, 2], [2, 0]] order = [] ``` ```text nodeCount = 5 edges = [] order = [0, 1, 2, 3, 4] ``` ### Discussion Requirements - State the invariant for prerequisite counts as nodes are emitted. - Explain why a FIFO queue can return a valid order without guaranteeing the lexicographically smallest one. - Explain how duplicate edges are deduplicated or counted and released consistently. - Test a self-loop, disconnected components, multiple simultaneous choices, isolated nodes, and a near-maximum sparse graph.

Quick Answer: Return the lexicographically smallest valid ordering of a directed dependency graph, or an empty result when a cycle exists. The problem tests deterministic graph processing, duplicate-edge handling, isolated nodes, and rigorous complexity analysis.

Implement `topologicalOrder(nodeCount, edges)`. A directed graph has nodes numbered `0` through `nodeCount - 1`. Each entry of `edges` is a two-element array `[from, to]` meaning `from` must appear before `to` in the returned order. Return the **lexicographically smallest** valid topological ordering of all `nodeCount` nodes: among every valid ordering, at the first index where two of them differ, the answer is the one holding the smaller node ID. This rule makes the answer unique, so returning a merely *valid* order is not enough. Return an empty array when the graph contains a directed cycle. A self-loop `[x, x]` is a cycle. When `nodeCount == 0` the answer is also the empty array. Duplicate edges may appear; a repeated pair states the same precedence constraint and must not change the answer. Isolated nodes (no incoming and no outgoing edges) still appear in the result. Do not modify `edges`. ### Output semantics - The result is an array of integers, and its order is graded exactly. - On success it is a permutation of `0 .. nodeCount - 1` of length `nodeCount`. - On any cycle it is exactly `[]`, even when part of the graph is acyclic. ### Examples Example 1: ```text nodeCount = 4 edges = [[0, 2], [1, 2], [1, 3]] returns [0, 1, 2, 3] ``` Nodes `0` and `1` start with no prerequisites; `0` is smaller, so it goes first. After `1` is emitted both `2` and `3` are free, and `2` is smaller. Example 2: ```text nodeCount = 4 edges = [[2, 0]] returns [1, 2, 0, 3] ``` Only node `0` has a prerequisite. The available set begins as `{1, 2, 3}`, so `1` is emitted, then `2`, which releases `0`. Because `0` is now available and smaller than `3`, it precedes `3`. Note that a FIFO queue would answer `[1, 2, 3, 0]`, which is valid but not the smallest. Example 3: ```text nodeCount = 3 edges = [[0, 1], [1, 2], [2, 0]] returns [] ``` The three nodes form a directed cycle, so no valid ordering exists.

Constraints

  • 0 <= nodeCount <= 12,000
  • 0 <= edges.length <= 20,000
  • edges[i].length == 2 and each edge is [from, to]
  • 0 <= edges[i][0] < nodeCount and 0 <= edges[i][1] < nodeCount
  • Duplicate edges are allowed and express the same precedence constraint
  • Self-loops are allowed in the input and are cycles
  • Let B be the compact UTF-8 JSON byte length of [nodeCount, edges], counting every bracket, comma, and digit: B <= 160,000
  • Let R be the compact UTF-8 JSON byte length of the returned integer array: R <= 80,000, so serialized input plus result is at most 240,000 bytes
  • Every value in the input and the result is a node ID in [0, 11,999], so all arithmetic fits in a 32-bit signed integer; no 64-bit widening is needed
  • Target O((nodeCount + edges.length) log nodeCount) time and O(nodeCount + edges.length) auxiliary space, or better

Examples

Input: (0, [])

Expected Output: []

Input: (1, [])

Expected Output: [0]

Hints

  1. Track, for every node, how many prerequisites are still unemitted. A node becomes selectable exactly when that count reaches zero, and it can only reach zero once.
  2. The tie-break is the whole problem. Among all currently selectable nodes you must always take the smallest ID, which is a different question from 'take whichever became selectable first' — think about which container answers it in logarithmic time.
  3. You never need a separate cycle search. Compare how many nodes you managed to emit against nodeCount; anything left over is trapped behind a cycle.

Loading coding console...