DSA-104 · Construct a topological order by discharging incoming edge occurrences

Course Schedule II — Ordering

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 133155 deterministic checks. Learner drafts are not executed.

Understand the problem

Return an ordering containing every course exactly once with each prerequisite before its dependent. Return a fresh empty int array if no complete order exists.

n is a nonnegative course count with labels 0..n-1. At most 100,000 vertices and 200,000 dependency occurrences are size preconditions. A negative n throws IllegalArgumentException; a null pair array throws NullPointerException. Reject null rows, rows whose length is not two, and out-of-range endpoints with IllegalArgumentException before traversal.
Each pair is [course, prerequisite], so the directed edge is prerequisite → course. Self-dependencies are valid graph data but make completion impossible. Duplicate pairs count as separate occurrences and are removed with matching multiplicity. Input rows may alias because the API is read-only.
Return any valid complete order, not necessarily the lexicographically smallest. The implementation seeds a FIFO in ascending label order and scans adjacency occurrences in input order. A zero-course input returns a fresh empty array successfully; its shape is intentionally the same as failure. Preserve the outer input, rows, and every value; allocate independent result arrays across calls.

Examples

Input: n=5, pairs=[[1,0],[2,0],[3,1],[3,2]]
Output: [0,4,1,2,3] for this FIFO implementation
Course 4 is initially ready and stays ahead of newly released courses 1 and 2. Other dependency-respecting permutations are valid.
Input: n=4, pairs=[[1,0],[0,1],[3,2]]
Output: []
The algorithm may process 2 and 3, but the remaining cycle prevents a complete order.
Input: n=0, pairs=[]
Output: []
An empty universe has one empty ordering; no course needs processing.

Before you start

Directed edges, adjacency lists, and incoming degree
FIFO discovery ownership and cycle obstruction

Recognize the structure

The output is a permutation subject to before/after inequalities. This is stronger than a feasibility boolean: retain the removed labels, but return them only if the entire vertex set is processed. Independent components and initially isolated vertices still belong in the output.

Try before revealing

Hint 1

Turn each pair into prerequisite → dependent.

Hint 2

Track the number of unmet incoming occurrences and seed every zero.

Hint 3

Append FIFO removals, discharge outgoing occurrences, and reject an incomplete prefix.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Rescan every dependency before selecting one course

Maintain a placed flag for each course. In each round mark every unplaced course provisionally eligible, then scan every pair and block its dependent when the prerequisite is unplaced. Select the least eligible label and repeat. This compiles without adjacency construction, but repeats O(V+E) work for up to V rounds. It can return a different valid order than the FIFO solution.

Improve the baseline

Replace repeated eligibility scans with counts

Build outgoing[prerequisite] and increment indegree[course] for every pair occurrence. A zero degree represents no unmet prerequisite occurrences.

Own each transition to readiness once

Seed all initial zeroes. Pop a course, append it, then decrement each outgoing neighbor. Enqueue only on the transition to exactly zero; duplicates must not enqueue a course early.

Certify completeness before exposing the permutation

Keep a count of appended labels. If count<n after exhaustion, discard the partial prefix and return a fresh empty array. Otherwise the n-entry result is complete.

Why it is correct

Legal-prefix invariant

At each stable loop boundary the emitted labels are distinct and satisfy every incoming dependency among them. Each ready course has no prerequisite outside the emitted prefix, so appending it preserves legality. During edge-by-edge trace states, the current course can still have pending outgoing occurrences to discharge.

No missing legal choice

Every initially zero course is seeded. Later a course becomes ready exactly when its last incoming occurrence is discharged. No course is scheduled twice, and the FIFO eventually processes every ready course.

Why exhaustion detects a cycle

If a nonempty residual graph has no zero-indegree vertex, repeatedly follow a residual incoming edge. Finiteness forces a repeated vertex and hence a cycle. Conversely a cycle cannot supply its own first ready vertex. A residual vertex can be downstream of a cycle without itself lying on it.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static void validate(int n,int[][] pairs) {
        if(n<0)throw new IllegalArgumentException("negative course count");Objects.requireNonNull(pairs,"pairs");
        for(int[] pair:pairs)if(pair==null||pair.length!=2||pair[0]<0||pair[0]>=n||pair[1]<0||pair[1]>=n)throw new IllegalArgumentException("invalid dependency");
    }
    public static int[] order(int n,int[][] prerequisites) {
        validate(n,prerequisites);List<List<Integer>> outgoing=new ArrayList<>();for(int i=0;i<n;i++)outgoing.add(new ArrayList<>());
        int[] indegree=new int[n];for(int[] pair:prerequisites){outgoing.get(pair[1]).add(pair[0]);indegree[pair[0]]++;}
        ArrayDeque<Integer> ready=new ArrayDeque<>();for(int course=0;course<n;course++)if(indegree[course]==0)ready.addLast(course);
        int[] result=new int[n];int count=0;
        while(!ready.isEmpty()) {
            int course=ready.removeFirst();result[count++]=course;
            for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);
        }
        return count==n?result:new int[0];
    }
    public static int[] baseline(int n,int[][] prerequisites) {
        validate(n,prerequisites);boolean[] placed=new boolean[n];int[] result=new int[n];
        for(int count=0;count<n;count++) {
            boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!placed[v];
            for(int[] pair:prerequisites)if(!placed[pair[1]])eligible[pair[0]]=false;
            int chosen=-1;for(int v=0;v<n;v++)if(eligible[v]){chosen=v;break;}
            if(chosen<0)return new int[0];placed[chosen]=true;result[count]=chosen;
        }
        return result;
    }
}

Read the meaningful blocks

The pair direction is part of the API

outgoing.get(pair[1]).add(pair[0]) implements [course, prerequisite]. Reversing this line returns an ordering for the opposite constraints.

Append at removal, not at discovery

The result prefix records processed labels. The queue is ready work, not an output sorted by numeric ID. Array allocation is fresh even on an empty result.

Compare valid permutations by constraints

The independent tests compare identity coverage and edge ranks rather than demanding one arbitrary ordering. Trace adapters additionally compare the deterministic FIFO sequence produced for each displayed fixture.

Complexity

For V=n and E pair occurrences, main time is O(V+E+1). Adjacency lists, degrees, and queue use O(V+E+1) auxiliary storage, excluding the O(V) successful output. A failure also abandons the private partially filled V-entry array before returning a fresh empty one.

The rescanning baseline costs O(V(V+E)+V+E+1) time and O(V+1) auxiliary flags excluding its result. The extra initialization/validation terms cover V=0 and empty arrays. Neither algorithm relies on recursion, so the main method supports a 100,000-course chain.

Exact-state walkthroughs

Reveal normal and boundary traces

FIFO order includes isolated courses

Input: {"n":5,"pairs":[[1,0],[2,0],[3,1],[3,2]]} · One complete course order / empty array: [0,4,1,2,3]

Step 1 of 12: Seed all courses with no unmet prerequisites.

Remaining indegree counts original edge occurrences, including duplicates; every zero is scheduled once. Pair direction follows this API’s explicit contract.

Course order — incoming prerequisites and one legal prefix

Phase: seed.

Pairs are [course, prerequisite]; edges go prerequisite → course.

Vertices — counts include pending edge releases of the current removal

00 incoming remainingoriginal successors: 1, 2
11 incoming remainingoriginal successors: 3
21 incoming remainingoriginal successors: 3
32 incoming remainingoriginal successors: (none)
40 incoming remainingoriginal successors: (none)

Ready FIFO — front at left; newly ready entries append

Removed vertices — teaching history

Empty.

Legal course prefix — returned only after full completion

Empty.

Processed: 0 of 5. This FIFO gives one valid order. It does not promise the smallest ordering. On a cycle, the returned empty array discards this partial prefix. A zero-course input also returns an empty array successfully.

Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.

State after this step
Variable	Value
n	`5`
pairs	`[[1,0],[2,0],[3,1],[3,2]]`
graph	`null`
outgoing	`[[1,2],[3],[3],[],[]]`
reverse	`[[],[],[],[],[]]`
remaining	`[0,1,1,2,0]`
ready	`[0,4]`
removed	`[]`
order	`[]`
safe	`[false,false,false,false,false]`
completed	`0`
semesters	`0`
leftInLayer	`0`
current	`null`
phase	`"seed"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] pairs) {
 4         if(n<0)throw new IllegalArgumentException("negative course count");Objects.requireNonNull(pairs,"pairs");
 5         for(int[] pair:pairs)if(pair==null||pair.length!=2||pair[0]<0||pair[0]>=n||pair[1]<0||pair[1]>=n)throw new IllegalArgumentException("invalid dependency");
 6     }
 7     public static int[] order(int n,int[][] prerequisites) {
 8         validate(n,prerequisites);List<List<Integer>> outgoing=new ArrayList<>();for(int i=0;i<n;i++)outgoing.add(new ArrayList<>());
 9         int[] indegree=new int[n];for(int[] pair:prerequisites){outgoing.get(pair[1]).add(pair[0]);indegree[pair[0]]++;}
10         ArrayDeque<Integer> ready=new ArrayDeque<>();for(int course=0;course<n;course++)if(indegree[course]==0)ready.addLast(course);
11         int[] result=new int[n];int count=0;
12         while(!ready.isEmpty()) {
13             int course=ready.removeFirst();result[count++]=course;
14             for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);
15         }
16         return count==n?result:new int[0];
17     }
18     public static int[] baseline(int n,int[][] prerequisites) {
19         validate(n,prerequisites);boolean[] placed=new boolean[n];int[] result=new int[n];
20         for(int count=0;count<n;count++) {
21             boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!placed[v];
22             for(int[] pair:prerequisites)if(!placed[pair[1]])eligible[pair[0]]=false;
23             int chosen=-1;for(int v=0;v<n;v++)if(eligible[v]){chosen=v;break;}
24             if(chosen<0)return new int[0];placed[chosen]=true;result[count]=chosen;
25         }
26         return result;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed all courses with no unmet prerequisites.
Remaining indegree counts original edge occurrences, including duplicates; every zero is scheduled once. Pair direction follows this API’s explicit contract.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,1,1,2,0]
ready
[0,4]
removed
[]
order
[]
safe
[false,false,false,false,false]
completed
0
semesters
0
leftInLayer
0
current
null
phase
"seed"
Take one ready course and discharge its outgoing dependencies.
The removed vertex has zero unmet incoming occurrences; new zero counts enter the queue after existing entries.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,1,1,2,0]
ready
[4]
removed
[0]
order
[0]
safe
[false,false,false,false,false]
completed
1
semesters
0
leftInLayer
0
current
0
phase
"remove"
Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,0,1,2,0]
ready
[4,1]
removed
[0]
order
[0]
safe
[false,false,false,false,false]
completed
1
semesters
0
leftInLayer
0
current
0
phase
"release"
next
1
edgeIndex
0
Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,0,0,2,0]
ready
[4,1,2]
removed
[0]
order
[0]
safe
[false,false,false,false,false]
completed
1
semesters
0
leftInLayer
0
current
0
phase
"release"
next
2
edgeIndex
1
Take one ready course and discharge its outgoing dependencies.
The removed vertex has zero unmet incoming occurrences; new zero counts enter the queue after existing entries.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,0,0,2,0]
ready
[1,2]
removed
[0,4]
order
[0,4]
safe
[false,false,false,false,false]
completed
2
semesters
0
leftInLayer
0
current
4
phase
"remove"
Take one ready course and discharge its outgoing dependencies.
The removed vertex has zero unmet incoming occurrences; new zero counts enter the queue after existing entries.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,0,0,2,0]
ready
[2]
removed
[0,4,1]
order
[0,4,1]
safe
[false,false,false,false,false]
completed
3
semesters
0
leftInLayer
0
current
1
phase
"remove"
Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,0,0,1,0]
ready
[2]
removed
[0,4,1]
order
[0,4,1]
safe
[false,false,false,false,false]
completed
3
semesters
0
leftInLayer
0
current
1
phase
"release"
next
3
edgeIndex
0
Take one ready course and discharge its outgoing dependencies.
The removed vertex has zero unmet incoming occurrences; new zero counts enter the queue after existing entries.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,0,0,1,0]
ready
[]
removed
[0,4,1,2]
order
[0,4,1,2]
safe
[false,false,false,false,false]
completed
4
semesters
0
leftInLayer
0
current
2
phase
"remove"
Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,0,0,0,0]
ready
[3]
removed
[0,4,1,2]
order
[0,4,1,2]
safe
[false,false,false,false,false]
completed
4
semesters
0
leftInLayer
0
current
2
phase
"release"
next
3
edgeIndex
0
Take one ready course and discharge its outgoing dependencies.
The removed vertex has zero unmet incoming occurrences; new zero counts enter the queue after existing entries.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,0,0,0,0]
ready
[]
removed
[0,4,1,2,3]
order
[0,4,1,2,3]
safe
[false,false,false,false,false]
completed
5
semesters
0
leftInLayer
0
current
3
phase
"remove"
Every course was processed.
Queue exhaustion with vertices left proves a cycle exists in the residual graph; it does not prove every residual vertex lies on a cycle.
n
5
pairs
[[1,0],[2,0],[3,1],[3,2]]
graph
null
outgoing
[[1,2],[3],[3],[],[]]
reverse
[[],[],[],[],[]]
remaining
[0,0,0,0,0]
ready
[]
removed
[0,4,1,2,3]
order
[0,4,1,2,3]
safe
[false,false,false,false,false]
completed
5
semesters
0
leftInLayer
0
current
null
phase
"complete"
Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
result
[0,4,1,2,3]

Duplicate incoming occurrences discharge separately

Input: {"n":3,"pairs":[[1,0],[1,0],[2,1]]} · One complete course order / empty array: [0,1,2]

Step 1 of 9: Seed all courses with no unmet prerequisites.

Remaining indegree counts original edge occurrences, including duplicates; every zero is scheduled once. Pair direction follows this API’s explicit contract.

Course order — incoming prerequisites and one legal prefix

Phase: seed.

Pairs are [course, prerequisite]; edges go prerequisite → course.

Vertices — counts include pending edge releases of the current removal

00 incoming remainingoriginal successors: 1, 1
12 incoming remainingoriginal successors: 2
21 incoming remainingoriginal successors: (none)

Ready FIFO — front at left; newly ready entries append

Removed vertices — teaching history

Empty.

Legal course prefix — returned only after full completion

Empty.

Processed: 0 of 3. This FIFO gives one valid order. It does not promise the smallest ordering. On a cycle, the returned empty array discards this partial prefix. A zero-course input also returns an empty array successfully.

Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.

State after this step
Variable	Value
n	`3`
pairs	`[[1,0],[1,0],[2,1]]`
graph	`null`
outgoing	`[[1,1],[2],[]]`
reverse	`[[],[],[]]`
remaining	`[0,2,1]`
ready	`[0]`
removed	`[]`
order	`[]`
safe	`[false,false,false]`
completed	`0`
semesters	`0`
leftInLayer	`0`
current	`null`
phase	`"seed"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] pairs) {
 4         if(n<0)throw new IllegalArgumentException("negative course count");Objects.requireNonNull(pairs,"pairs");
 5         for(int[] pair:pairs)if(pair==null||pair.length!=2||pair[0]<0||pair[0]>=n||pair[1]<0||pair[1]>=n)throw new IllegalArgumentException("invalid dependency");
 6     }
 7     public static int[] order(int n,int[][] prerequisites) {
 8         validate(n,prerequisites);List<List<Integer>> outgoing=new ArrayList<>();for(int i=0;i<n;i++)outgoing.add(new ArrayList<>());
 9         int[] indegree=new int[n];for(int[] pair:prerequisites){outgoing.get(pair[1]).add(pair[0]);indegree[pair[0]]++;}
10         ArrayDeque<Integer> ready=new ArrayDeque<>();for(int course=0;course<n;course++)if(indegree[course]==0)ready.addLast(course);
11         int[] result=new int[n];int count=0;
12         while(!ready.isEmpty()) {
13             int course=ready.removeFirst();result[count++]=course;
14             for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);
15         }
16         return count==n?result:new int[0];
17     }
18     public static int[] baseline(int n,int[][] prerequisites) {
19         validate(n,prerequisites);boolean[] placed=new boolean[n];int[] result=new int[n];
20         for(int count=0;count<n;count++) {
21             boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!placed[v];
22             for(int[] pair:prerequisites)if(!placed[pair[1]])eligible[pair[0]]=false;
23             int chosen=-1;for(int v=0;v<n;v++)if(eligible[v]){chosen=v;break;}
24             if(chosen<0)return new int[0];placed[chosen]=true;result[count]=chosen;
25         }
26         return result;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed all courses with no unmet prerequisites.
Remaining indegree counts original edge occurrences, including duplicates; every zero is scheduled once. Pair direction follows this API’s explicit contract.
n
3
pairs
[[1,0],[1,0],[2,1]]
graph
null
outgoing
[[1,1],[2],[]]
reverse
[[],[],[]]
remaining
[0,2,1]
ready
[0]
removed
[]
order
[]
safe
[false,false,false]
completed
0
semesters
0
leftInLayer
0
current
null
phase
"seed"
Take one ready course and discharge its outgoing dependencies.
The removed vertex has zero unmet incoming occurrences; new zero counts enter the queue after existing entries.
n
3
pairs
[[1,0],[1,0],[2,1]]
graph
null
outgoing
[[1,1],[2],[]]
reverse
[[],[],[]]
remaining
[0,2,1]
ready
[]
removed
[0]
order
[0]
safe
[false,false,false]
completed
1
semesters
0
leftInLayer
0
current
0
phase
"remove"
Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
n
3
pairs
[[1,0],[1,0],[2,1]]
graph
null
outgoing
[[1,1],[2],[]]
reverse
[[],[],[]]
remaining
[0,1,1]
ready
[]
removed
[0]
order
[0]
safe
[false,false,false]
completed
1
semesters
0
leftInLayer
0
current
0
phase
"release"
next
1
edgeIndex
0
Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
n
3
pairs
[[1,0],[1,0],[2,1]]
graph
null
outgoing
[[1,1],[2],[]]
reverse
[[],[],[]]
remaining
[0,0,1]
ready
[1]
removed
[0]
order
[0]
safe
[false,false,false]
completed
1
semesters
0
leftInLayer
0
current
0
phase
"release"
next
1
edgeIndex
1
Take one ready course and discharge its outgoing dependencies.
The removed vertex has zero unmet incoming occurrences; new zero counts enter the queue after existing entries.
n
3
pairs
[[1,0],[1,0],[2,1]]
graph
null
outgoing
[[1,1],[2],[]]
reverse
[[],[],[]]
remaining
[0,0,1]
ready
[]
removed
[0,1]
order
[0,1]
safe
[false,false,false]
completed
2
semesters
0
leftInLayer
0
current
1
phase
"remove"
Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
n
3
pairs
[[1,0],[1,0],[2,1]]
graph
null
outgoing
[[1,1],[2],[]]
reverse
[[],[],[]]
remaining
[0,0,0]
ready
[2]
removed
[0,1]
order
[0,1]
safe
[false,false,false]
completed
2
semesters
0
leftInLayer
0
current
1
phase
"release"
next
2
edgeIndex
0
Take one ready course and discharge its outgoing dependencies.
The removed vertex has zero unmet incoming occurrences; new zero counts enter the queue after existing entries.
n
3
pairs
[[1,0],[1,0],[2,1]]
graph
null
outgoing
[[1,1],[2],[]]
reverse
[[],[],[]]
remaining
[0,0,0]
ready
[]
removed
[0,1,2]
order
[0,1,2]
safe
[false,false,false]
completed
3
semesters
0
leftInLayer
0
current
2
phase
"remove"
Every course was processed.
Queue exhaustion with vertices left proves a cycle exists in the residual graph; it does not prove every residual vertex lies on a cycle.
n
3
pairs
[[1,0],[1,0],[2,1]]
graph
null
outgoing
[[1,1],[2],[]]
reverse
[[],[],[]]
remaining
[0,0,0]
ready
[]
removed
[0,1,2]
order
[0,1,2]
safe
[false,false,false]
completed
3
semesters
0
leftInLayer
0
current
null
phase
"complete"
Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
result
[0,1,2]

A valid prefix does not repair a separate cycle

Input: {"n":4,"pairs":[[1,0],[0,1],[3,2]]} · One complete course order / empty array: []

Step 1 of 6: Seed all courses with no unmet prerequisites.

Remaining indegree counts original edge occurrences, including duplicates; every zero is scheduled once. Pair direction follows this API’s explicit contract.

Course order — incoming prerequisites and one legal prefix

Phase: seed.

Pairs are [course, prerequisite]; edges go prerequisite → course.

Vertices — counts include pending edge releases of the current removal

01 incoming remainingoriginal successors: 1
11 incoming remainingoriginal successors: 0
20 incoming remainingoriginal successors: 3
31 incoming remainingoriginal successors: (none)

Ready FIFO — front at left; newly ready entries append

Removed vertices — teaching history

Empty.

Legal course prefix — returned only after full completion

Empty.

Processed: 0 of 4. This FIFO gives one valid order. It does not promise the smallest ordering. On a cycle, the returned empty array discards this partial prefix. A zero-course input also returns an empty array successfully.

Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.

State after this step
Variable	Value
n	`4`
pairs	`[[1,0],[0,1],[3,2]]`
graph	`null`
outgoing	`[[1],[0],[3],[]]`
reverse	`[[],[],[],[]]`
remaining	`[1,1,0,1]`
ready	`[2]`
removed	`[]`
order	`[]`
safe	`[false,false,false,false]`
completed	`0`
semesters	`0`
leftInLayer	`0`
current	`null`
phase	`"seed"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] pairs) {
 4         if(n<0)throw new IllegalArgumentException("negative course count");Objects.requireNonNull(pairs,"pairs");
 5         for(int[] pair:pairs)if(pair==null||pair.length!=2||pair[0]<0||pair[0]>=n||pair[1]<0||pair[1]>=n)throw new IllegalArgumentException("invalid dependency");
 6     }
 7     public static int[] order(int n,int[][] prerequisites) {
 8         validate(n,prerequisites);List<List<Integer>> outgoing=new ArrayList<>();for(int i=0;i<n;i++)outgoing.add(new ArrayList<>());
 9         int[] indegree=new int[n];for(int[] pair:prerequisites){outgoing.get(pair[1]).add(pair[0]);indegree[pair[0]]++;}
10         ArrayDeque<Integer> ready=new ArrayDeque<>();for(int course=0;course<n;course++)if(indegree[course]==0)ready.addLast(course);
11         int[] result=new int[n];int count=0;
12         while(!ready.isEmpty()) {
13             int course=ready.removeFirst();result[count++]=course;
14             for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);
15         }
16         return count==n?result:new int[0];
17     }
18     public static int[] baseline(int n,int[][] prerequisites) {
19         validate(n,prerequisites);boolean[] placed=new boolean[n];int[] result=new int[n];
20         for(int count=0;count<n;count++) {
21             boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!placed[v];
22             for(int[] pair:prerequisites)if(!placed[pair[1]])eligible[pair[0]]=false;
23             int chosen=-1;for(int v=0;v<n;v++)if(eligible[v]){chosen=v;break;}
24             if(chosen<0)return new int[0];placed[chosen]=true;result[count]=chosen;
25         }
26         return result;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed all courses with no unmet prerequisites.
Remaining indegree counts original edge occurrences, including duplicates; every zero is scheduled once. Pair direction follows this API’s explicit contract.
n
4
pairs
[[1,0],[0,1],[3,2]]
graph
null
outgoing
[[1],[0],[3],[]]
reverse
[[],[],[],[]]
remaining
[1,1,0,1]
ready
[2]
removed
[]
order
[]
safe
[false,false,false,false]
completed
0
semesters
0
leftInLayer
0
current
null
phase
"seed"
Take one ready course and discharge its outgoing dependencies.
The removed vertex has zero unmet incoming occurrences; new zero counts enter the queue after existing entries.
n
4
pairs
[[1,0],[0,1],[3,2]]
graph
null
outgoing
[[1],[0],[3],[]]
reverse
[[],[],[],[]]
remaining
[1,1,0,1]
ready
[]
removed
[2]
order
[2]
safe
[false,false,false,false]
completed
1
semesters
0
leftInLayer
0
current
2
phase
"remove"
Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
n
4
pairs
[[1,0],[0,1],[3,2]]
graph
null
outgoing
[[1],[0],[3],[]]
reverse
[[],[],[],[]]
remaining
[1,1,0,0]
ready
[3]
removed
[2]
order
[2]
safe
[false,false,false,false]
completed
1
semesters
0
leftInLayer
0
current
2
phase
"release"
next
3
edgeIndex
0
Take one ready course and discharge its outgoing dependencies.
The removed vertex has zero unmet incoming occurrences; new zero counts enter the queue after existing entries.
n
4
pairs
[[1,0],[0,1],[3,2]]
graph
null
outgoing
[[1],[0],[3],[]]
reverse
[[],[],[],[]]
remaining
[1,1,0,0]
ready
[]
removed
[2,3]
order
[2,3]
safe
[false,false,false,false]
completed
2
semesters
0
leftInLayer
0
current
3
phase
"remove"
An unprocessed cycle prevents complete scheduling.
Queue exhaustion with vertices left proves a cycle exists in the residual graph; it does not prove every residual vertex lies on a cycle.
n
4
pairs
[[1,0],[0,1],[3,2]]
graph
null
outgoing
[[1],[0],[3],[]]
reverse
[[],[],[],[]]
remaining
[1,1,0,0]
ready
[]
removed
[2,3]
order
[2,3]
safe
[false,false,false,false]
completed
2
semesters
0
leftInLayer
0
current
null
phase
"cycle"
Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
result
[]

Empty course universe

Input: {"n":0,"pairs":[]} · One complete course order / empty array: []

Step 1 of 3: Seed all courses with no unmet prerequisites.

Remaining indegree counts original edge occurrences, including duplicates; every zero is scheduled once. Pair direction follows this API’s explicit contract.

Course order — incoming prerequisites and one legal prefix

Phase: seed.

Pairs are [course, prerequisite]; edges go prerequisite → course.

Vertices — counts include pending edge releases of the current removal

Ready FIFO — front at left; newly ready entries append

Empty.

Removed vertices — teaching history

Empty.

Legal course prefix — returned only after full completion

Empty.

Processed: 0 of 0. This FIFO gives one valid order. It does not promise the smallest ordering. On a cycle, the returned empty array discards this partial prefix. A zero-course input also returns an empty array successfully.

Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.

State after this step
Variable	Value
n	`0`
pairs	`[]`
graph	`null`
outgoing	`[]`
reverse	`[]`
remaining	`[]`
ready	`[]`
removed	`[]`
order	`[]`
safe	`[]`
completed	`0`
semesters	`0`
leftInLayer	`0`
current	`null`
phase	`"seed"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] pairs) {
 4         if(n<0)throw new IllegalArgumentException("negative course count");Objects.requireNonNull(pairs,"pairs");
 5         for(int[] pair:pairs)if(pair==null||pair.length!=2||pair[0]<0||pair[0]>=n||pair[1]<0||pair[1]>=n)throw new IllegalArgumentException("invalid dependency");
 6     }
 7     public static int[] order(int n,int[][] prerequisites) {
 8         validate(n,prerequisites);List<List<Integer>> outgoing=new ArrayList<>();for(int i=0;i<n;i++)outgoing.add(new ArrayList<>());
 9         int[] indegree=new int[n];for(int[] pair:prerequisites){outgoing.get(pair[1]).add(pair[0]);indegree[pair[0]]++;}
10         ArrayDeque<Integer> ready=new ArrayDeque<>();for(int course=0;course<n;course++)if(indegree[course]==0)ready.addLast(course);
11         int[] result=new int[n];int count=0;
12         while(!ready.isEmpty()) {
13             int course=ready.removeFirst();result[count++]=course;
14             for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);
15         }
16         return count==n?result:new int[0];
17     }
18     public static int[] baseline(int n,int[][] prerequisites) {
19         validate(n,prerequisites);boolean[] placed=new boolean[n];int[] result=new int[n];
20         for(int count=0;count<n;count++) {
21             boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!placed[v];
22             for(int[] pair:prerequisites)if(!placed[pair[1]])eligible[pair[0]]=false;
23             int chosen=-1;for(int v=0;v<n;v++)if(eligible[v]){chosen=v;break;}
24             if(chosen<0)return new int[0];placed[chosen]=true;result[count]=chosen;
25         }
26         return result;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed all courses with no unmet prerequisites.
Remaining indegree counts original edge occurrences, including duplicates; every zero is scheduled once. Pair direction follows this API’s explicit contract.
n
0
pairs
[]
graph
null
outgoing
[]
reverse
[]
remaining
[]
ready
[]
removed
[]
order
[]
safe
[]
completed
0
semesters
0
leftInLayer
0
current
null
phase
"seed"
Every course was processed.
Queue exhaustion with vertices left proves a cycle exists in the residual graph; it does not prove every residual vertex lies on a cycle.
n
0
pairs
[]
graph
null
outgoing
[]
reverse
[]
remaining
[]
ready
[]
removed
[]
order
[]
safe
[]
completed
0
semesters
0
leftInLayer
0
current
null
phase
"complete"
Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
result
[]

Test the contract

Input: No courses and no pairs
Output: fresh []
Valid empty order.
Input: Duplicate [1,0] rows, including shared row objects
Output: one occurrence of each course in a valid order
Occurrence counts are consistent and input remains unchanged.
Input: Self-loop or cycle plus a free component
Output: []
Partial progress is not full feasibility.
Input: 100,000-course chain
Output: [0,1,...,99999]
Main path uses no recursive call stack.
Input: Null/ragged/out-of-range pair
Output: documented exception before traversal
Malformed data is different from a valid but cyclic graph.

Common mistakes and counterexamples

Read the pair backward

Counterexample: [[1,0]] requires 0 before 1, not 1 before 0.

Name the prerequisite source and dependent destination before building the edge.

Return the partial prefix on a cycle

Counterexample: A separate 2→3 component can finish while 0↔1 remains blocked.

Require count==n before returning the successful order.

Treat FIFO as a smallest-order guarantee

Counterexample: With isolated 4 initially ready, the shown result is [0,4,1,2,3].

Accept any valid permutation; use a min-priority queue only if smallest order is required.

Deduplicate only one representation

Counterexample: One stored edge with degree two leaves the dependent blocked forever.

Retain both occurrences in both representations, or deduplicate both consistently.

Follow-ups

Return the lexicographically smallest valid order.

Replace the FIFO with a min-priority queue and prove greedy prefix optimality. Sorting only the initial queue does not order newly released labels against existing entries.

Return a concrete directed cycle.

Keep this order API separate from cycle extraction. Run an iterative active/finished DFS on the residual graph with parent/continuation state; leftover vertices alone do not form an ordered cycle witness.

Explain which courses can run in parallel.

Freeze complete ready batches or compute earliest prerequisite levels. An arbitrary topological permutation alone does not encode semester boundaries or processor capacity.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 166/20,000 characters

Self-review

Can I explain why [course, prerequisite] reverses when forming the edge?Can I prove every emitted course has all prerequisites earlier?Can I distinguish ready order, output order, cycle failure, and valid empty input?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform parity claims.