Quick Overview

A graph coding question on prerequisite ordering: given n courses and pairs stating which course must come before another, return the lexicographically smallest order that satisfies every prerequisite, or an empty list when a cycle makes any order impossible. It tests dependency graphs, cycle detection and deterministic tie-breaking.

Course Prerequisite Ordering: Lexicographically Smallest Valid Order or Empty on a Cycle

Company: ByteDance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

There are `n` courses labelled `0` to `n - 1`. Each pair `[a, b]` in `prerequisites` means that course `b` must be taken before course `a`. Return an order in which all `n` courses can be taken, or an empty list if no order satisfies every prerequisite. The report identifies this coding question only as a medium-difficulty variant of a classic course-ordering problem and does not say what the variant changed. This version fixes one exact set of rules, including a tie rule that makes the answer unique. ### Function Signature ```python def course_order(n: int, prerequisites: list[list[int]]) -> list[int]: ``` ### Rules - A pair `[a, b]` means course `b` must appear before course `a` in the returned order. - A valid order lists every course from `0` to `n - 1` exactly once and places every course after all of its prerequisites. - When several valid orders exist, return the lexicographically smallest one: compare two orders position by position, and at the first position where they differ, the order with the smaller course label there is smaller. - If no valid order exists because the prerequisites form a cycle, return `[]`. - A pair may appear more than once; repeated pairs mean the same as a single copy. ### Constraints - `1 <= n <= 10^5` - `0 <= len(prerequisites) <= 2 * 10^5` - `0 <= a <= n - 1`, `0 <= b <= n - 1` and `a != b` for every pair ### Examples **Example 1** ```text Input: n = 5, prerequisites = [[0, 3], [2, 3], [2, 4], [1, 0]] Output: [3, 0, 1, 4, 2] ``` Every valid order places 3 before 0 and 2, places 4 before 2, and places 0 before 1. Other valid orders exist, such as `[3, 4, 0, 1, 2]` and `[4, 3, 2, 0, 1]`, but `[3, 0, 1, 4, 2]` is the lexicographically smallest. **Example 2** ```text Input: n = 3, prerequisites = [[0, 1], [1, 2], [2, 0]] Output: [] ``` Course 1 must precede 0, course 2 must precede 1, and course 0 must precede 2, which is a cycle. **Example 3** ```text Input: n = 3, prerequisites = [[0, 2], [0, 2]] Output: [1, 2, 0] ``` The repeated pair only requires 2 before 0. The valid orders are `[1, 2, 0]`, `[2, 0, 1]` and `[2, 1, 0]`, and the first is the smallest.

Overview: A graph coding question on prerequisite ordering: given n courses and pairs stating which course must come before another, return the lexicographically smallest order that satisfies every prerequisite, or an empty list when a cycle makes any order impossible. It tests dependency graphs, cycle detection and deterministic tie-breaking.

Read the full ByteDance Software Engineer interview experience this question came from

There are `n` courses labelled `0` to `n - 1`. Each pair `[a, b]` in `prerequisites` means that course `b` must be taken before course `a`. Return an order in which all `n` courses can be taken, or an empty list if no order satisfies every prerequisite. Implement `course_order(n, prerequisites)` under these rules: - A pair `[a, b]` means course `b` must appear before course `a` in the returned order. - A valid order lists every course from `0` to `n - 1` exactly once and places every course after all of its prerequisites. - When several valid orders exist, return the lexicographically smallest one: compare two orders position by position, and at the first position where they differ, the order with the smaller course label there is smaller. - If no valid order exists because the prerequisites form a cycle, return `[]`. - A pair may appear more than once; repeated pairs mean the same as a single copy. **Constraints** - `1 <= n <= 10^5` - `0 <= len(prerequisites) <= 2 * 10^5` - `0 <= a <= n - 1`, `0 <= b <= n - 1` and `a != b` for every pair - Every value fits in a 32-bit signed integer; no value exceeds 2^31 - 1. **Example 1** ```text Input: n = 5, prerequisites = [[0, 3], [2, 3], [2, 4], [1, 0]] Output: [3, 0, 1, 4, 2] ``` Every valid order places 3 before 0 and 2, places 4 before 2, and places 0 before 1. Other valid orders exist, such as `[3, 4, 0, 1, 2]` and `[4, 3, 2, 0, 1]`, but `[3, 0, 1, 4, 2]` is the lexicographically smallest. **Example 2** ```text Input: n = 3, prerequisites = [[0, 2], [0, 2]] Output: [1, 2, 0] ``` The repeated pair only requires 2 before 0. The valid orders are `[1, 2, 0]`, `[2, 0, 1]` and `[2, 1, 0]`, and the first is the smallest.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(prerequisites) <= 2 * 10^5
  • 0 <= a <= n - 1, 0 <= b <= n - 1 and a != b for every pair [a, b]
  • A pair may appear more than once; a repeated pair means the same as a single copy

Examples

Input: (1, [])

Expected Output: [0]

Explanation: Minimum valid: one course and no prerequisites.

Input: (4, [])

Expected Output: [0, 1, 2, 3]

Explanation: No prerequisites: every course is free, so the smallest order is the identity order.

Hints

  1. A course can be taken only after every course it depends on is already in the order; a repeated pair adds no extra requirement.
  2. Orders are compared from the first position, so the choice made at an earlier position outweighs every later one: think about which courses are allowed to sit at the current position.
  3. If at some point every remaining course still waits on another remaining course, no valid order exists.

Lexicographically Smallest Course Order

mediumByteDanceSoftware Engineer

There are n courses labelled 0 to n - 1. Each pair [a, b] in prerequisites means that course b must be taken before course a. Return an order in which all n courses can be taken, or an empty list if no order satisfies every prerequisite.

Implement course_order(n, prerequisites) under these rules:

  • A pair [a, b] means course b must appear before course a in the returned order.
  • A valid order lists every course from 0 to n - 1 exactly once and places every course after all of its prerequisites.
  • When several valid orders exist, return the lexicographically smallest one: compare two orders position by position, and at the first position where they differ, the order with the smaller course label there is smaller.
  • If no valid order exists because the prerequisites form a cycle, return [].
  • A pair may appear more than once; repeated pairs mean the same as a single copy.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(prerequisites) <= 2 * 10^5
  • 0 <= a <= n - 1, 0 <= b <= n - 1 and a != b for every pair
  • Every value fits in a 32-bit signed integer; no value exceeds 2^31 - 1.

Example 1

Input:  n = 5, prerequisites = [[0, 3], [2, 3], [2, 4], [1, 0]]
Output: [3, 0, 1, 4, 2]

Every valid order places 3 before 0 and 2, places 4 before 2, and places 0 before 1. Other valid orders exist, such as [3, 4, 0, 1, 2] and [4, 3, 2, 0, 1], but [3, 0, 1, 4, 2] is the lexicographically smallest.

Example 2

Input:  n = 3, prerequisites = [[0, 2], [0, 2]]
Output: [1, 2, 0]

The repeated pair only requires 2 before 0. The valid orders are [1, 2, 0], [2, 0, 1] and [2, 1, 0], and the first is the smallest.

Examples

Example 1
Input
(1, [])
Output
[0]
Notes
Minimum valid: one course and no prerequisites.
Example 2
Input
(4, [])
Output
[0, 1, 2, 3]
Notes
No prerequisites: every course is free, so the smallest order is the identity order.

Constraints

  • •1 <= n <= 10^5
  • •0 <= len(prerequisites) <= 2 * 10^5
  • •0 <= a <= n - 1, 0 <= b <= n - 1 and a != b for every pair [a, b]
  • •A pair may appear more than once; a repeated pair means the same as a single copy

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def course_order(n: int, prerequisites: list[list[int]]) -> list[int]:
Sample call
course_order(1, [])
Language
Case 1
Input
(1, [])
Expected
[0]
Case 2
Input
(4, [])
Expected
[0, 1, 2, 3]

Browse More Questions

Show the approach

Approach

Model the pairs as a directed graph with an edge b -> a for every pair [a, b] (b must come first), and give each course an in-degree equal to the number of stored pairs that name it as a, counting every copy. Run Kahn's algorithm with a min-heap instead of a FIFO queue: the heap always holds exactly the courses that are not yet placed and whose prerequisites have all been placed. Repeatedly pop the smallest such label, append it, and decrement the in-degree of every course that depends on it, pushing a course the moment its count reaches zero.

Invariant: the placed prefix is always valid, and the heap contains every unplaced course whose remaining in-degree is zero. Tie rule: while the unplaced courses form an acyclic graph, any currently available course can be placed next and the rest can still be completed, so the lexicographically smallest valid order must put the smallest available label at the current position; applying this at every position shows the greedy order is the unique smallest one. A FIFO queue or a DFS order is valid but can delay a newly unlocked small label behind older larger ones.

Duplicates: each copy of a pair adds one to the in-degree and contributes one decrement when its prerequisite is placed, so a course becomes available exactly when the last of its prerequisites is placed, the same as with a single copy. Cycles: no course on a cycle ever reaches in-degree zero, so fewer than n courses are placed and the function returns [] rather than the partial order.

Edge cases: n = 1 or an empty prerequisites list gives the identity order 0..n-1; a cycle in any component, even one disconnected from the rest, makes the whole answer [].

Time complexity:
O((n + m) log n), where m = len(prerequisites)
Space complexity:
O(n + m)