Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-107 · FOCUSED PRACTICE

Parallel Courses — Minimum Semesters

Core · Java 21 · Version 1 · editorial draft

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

Understand the problem

Return the minimum semesters required to finish all courses when any number of eligible courses may run in parallel. Return -1 if prerequisites make completion impossible.

  • 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 relation is [before, after] with zero-based labels, so before must finish in a strictly earlier semester than after. This differs from the [course, prerequisite] pair layout of DSA-104. Every course takes exactly one semester and capacity is unlimited. Self-loops and duplicate relations are permitted graph data; duplicates do not add extra semesters.
  • A course can start only when every prerequisite finished in a previous semester, not earlier in the same queue loop. Return 0 for n=0, 1 for nonempty courses with no dependencies, and -1 for any unfinishable component even if other courses complete. Preserve all caller pairs/row identities, including shared rows.

Examples

  1. Input: n=5, relations=[[0,2],[1,2],[2,3]]
    Output: 3

    Semester 1 takes 0,1,4; semester 2 takes 2; semester 3 takes 3. Independent work does not add semesters.

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

    Both 0→1 occurrences discharge together; 1 still waits until the next semester.

  3. Input: n=3, relations=[[0,1],[1,0]]
    Output: -1

    Course 2 can finish, but the remaining cycle prevents a full schedule.

Before you start

  • Topological indegrees and directed prerequisite edges
  • FIFO layer boundaries and earliest completion times

Recognize the structure

A topological order can serialize independent courses unnecessarily. The objective is elapsed parallel rounds with unlimited capacity and unit durations, so capture complete readiness layers. The optimum equals the longest prerequisite-chain length in vertices when the graph is acyclic.

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.

No unsaved text changes · 174/20,000 characters

Self-review

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

Try before revealing

Hint 1

Unlimited parallel work suggests complete readiness batches.

Hint 2

Use incoming counts, but freeze the queue length before each semester.

Hint 3

Compare the last batch number with longest prerequisite-chain length and verify full completion.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Recompute a semester’s eligible set from a completed snapshot

For each semester, provisionally mark uncompleted courses eligible, then scan every relation against the previous completed set. Only after the entire scan mark all eligible courses done. A round with no gain before full completion is impossible. This avoids graph construction but repeats a full eligibility scan per semester.

Improve the baseline

Build the direct prerequisite graph

Store outgoing[before] and increment indegree[after] for every relation occurrence. Seed every zero, including isolated courses.

Freeze the batch before removing anything

At the start of a round save size=ready.size() and increment semesters. Remove exactly size courses. Newly released courses append after this batch and are processed only by the next outer iteration.

Check total completion independently of elapsed rounds

Count all removals. Return semesters only if completed==n; otherwise return -1. A cycle plus free work can produce nonzero internal rounds and still require failure.

Why it is correct

Layer legality

Every first-layer course has no prerequisites. Inductively every newly released course has had all prerequisite occurrences discharged by completed courses. Freezing the batch delays it until a strictly later semester than its last completing prerequisite.

Lower bound from chains

A chain of k courses requires at least k semesters because each dependency enforces a strict semester increase. More generally a course cannot finish before one plus its latest prerequisite completion time.

Matching earliest schedule

Taking every eligible course immediately never consumes limited capacity because capacity is unlimited. Its completion semester is exactly 1+max(prerequisite semesters), or one for a source. This realizes every earliest completion bound, so the last layer equals the minimum makespan. Cycles cannot supply a first finished member.

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 minimumSemesters(int n,int[][] relations) {
        validate(n,relations);List<List<Integer>> outgoing=new ArrayList<>();for(int v=0;v<n;v++)outgoing.add(new ArrayList<>());int[] indegree=new int[n];
        for(int[] pair:relations){outgoing.get(pair[0]).add(pair[1]);indegree[pair[1]]++;}
        ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(indegree[v]==0)ready.addLast(v);int completed=0,semesters=0;
        while(!ready.isEmpty()) {
            int size=ready.size();semesters++;
            for(int i=0;i<size;i++){int course=ready.removeFirst();completed++;for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);}
        }
        return completed==n?semesters:-1;
    }
    public static int baseline(int n,int[][] relations) {
        validate(n,relations);boolean[] done=new boolean[n];int completed=0,semesters=0;
        while(completed<n){boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!done[v];for(int[] pair:relations)if(!done[pair[0]])eligible[pair[1]]=false;int gained=0;for(int v=0;v<n;v++)if(eligible[v]){done[v]=true;gained++;}if(gained==0)return -1;completed+=gained;semesters++;}return semesters;
    }
}

Read the meaningful blocks

Captured size is a semantic boundary

The for-loop count is the queue length before this semester. A loop that drains the growing queue would finish an entire dependency chain in one semester.

Completed count and semester count answer different questions

completed detects graph-wide feasibility, while semesters measures the longest layer chain. Neither can replace the other.

No implicit capacity or variable durations

The algorithm does not solve a k-courses-per-term limit or courses taking different durations. Those change the optimization state and proof.

Complexity

For V=n and E relation occurrences, main time is O(V+E+1). Adjacency, indegrees, and queue use O(V+E+1) auxiliary storage; the output is one int. The semester count is at most V for any feasible nonempty graph.

The snapshot baseline takes O(V(V+E)+V+E+1) worst-case time and O(V+1) auxiliary flags. Long chains attain V rounds, while an edgeless graph completes in one. Duplicate relations increase E work, not the optimal semester count.

Exact-state walkthroughs

Reveal normal and boundary traces

Independent courses share the first semester

Input: {"n":5,"pairs":[[0,2],[1,2],[2,3]]} · Minimum semesters / −1: 3

Step 1 of 14: 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.

Parallel semesters — frozen ready batches

Phase: seed.

Relations are [before, after]; both labels are zero-based.

Vertices — counts include pending edge releases of the current removal

  • 00 incoming remainingoriginal successors: 2
  • 10 incoming remainingoriginal successors: 2
  • 22 incoming remainingoriginal successors: 3
  • 31 incoming remainingoriginal successors: (none)
  • 40 incoming remainingoriginal successors: (none)

Ready FIFO — front at left; newly ready entries append

  • 0
  • 1
  • 4

Removed vertices — teaching history

Empty.

Semester number: 0. Pops remaining in this frozen semester: 0. Completed: 0 of 5. Only the captured batch can finish now; newly released courses wait until next semester. Capacity is unlimited and every course takes one semester. A residual cycle makes the final answer −1 even after partial progress.

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
VariableValue
n5
pairs[[0,2],[1,2],[2,3]]
graphnull
outgoing[[2],[2],[3],[],[]]
reverse[[],[],[],[],[]]
remaining[0,0,2,1,0]
ready[0,1,4]
removed[]
order[]
safe[false,false,false,false,false]
completed0
semesters0
leftInLayer0
currentnull
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 minimumSemesters(int n,int[][] relations) {
 8         validate(n,relations);List<List<Integer>> outgoing=new ArrayList<>();for(int v=0;v<n;v++)outgoing.add(new ArrayList<>());int[] indegree=new int[n];
 9         for(int[] pair:relations){outgoing.get(pair[0]).add(pair[1]);indegree[pair[1]]++;}
10         ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(indegree[v]==0)ready.addLast(v);int completed=0,semesters=0;
11         while(!ready.isEmpty()) {
12             int size=ready.size();semesters++;
13             for(int i=0;i<size;i++){int course=ready.removeFirst();completed++;for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);}
14         }
15         return completed==n?semesters:-1;
16     }
17     public static int baseline(int n,int[][] relations) {
18         validate(n,relations);boolean[] done=new boolean[n];int completed=0,semesters=0;
19         while(completed<n){boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!done[v];for(int[] pair:relations)if(!done[pair[0]])eligible[pair[1]]=false;int gained=0;for(int v=0;v<n;v++)if(eligible[v]){done[v]=true;gained++;}if(gained==0)return -1;completed+=gained;semesters++;}return semesters;
20     }
21 }
22

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

Read the full static trace
  1. 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
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,2,1,0]
    ready
    [0,1,4]
    removed
    []
    order
    []
    safe
    [false,false,false,false,false]
    completed
    0
    semesters
    0
    leftInLayer
    0
    current
    null
    phase
    "seed"
  2. Freeze the courses eligible before this semester starts.

    Only this captured number may finish now. A newly unlocked course requires its prerequisites to finish in an earlier semester.

    n
    5
    pairs
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,2,1,0]
    ready
    [0,1,4]
    removed
    []
    order
    []
    safe
    [false,false,false,false,false]
    completed
    0
    semesters
    1
    leftInLayer
    3
    current
    null
    phase
    "layer"
  3. 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
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,2,1,0]
    ready
    [1,4]
    removed
    [0]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    1
    semesters
    1
    leftInLayer
    2
    current
    0
    phase
    "remove"
  4. 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
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,1,1,0]
    ready
    [1,4]
    removed
    [0]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    1
    semesters
    1
    leftInLayer
    2
    current
    0
    phase
    "release"
    next
    2
    edgeIndex
    0
  5. 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
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,1,1,0]
    ready
    [4]
    removed
    [0,1]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    2
    semesters
    1
    leftInLayer
    1
    current
    1
    phase
    "remove"
  6. 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
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,0,1,0]
    ready
    [4,2]
    removed
    [0,1]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    2
    semesters
    1
    leftInLayer
    1
    current
    1
    phase
    "release"
    next
    2
    edgeIndex
    0
  7. 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
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,0,1,0]
    ready
    [2]
    removed
    [0,1,4]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    3
    semesters
    1
    leftInLayer
    0
    current
    4
    phase
    "remove"
  8. Freeze the courses eligible before this semester starts.

    Only this captured number may finish now. A newly unlocked course requires its prerequisites to finish in an earlier semester.

    n
    5
    pairs
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,0,1,0]
    ready
    [2]
    removed
    [0,1,4]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    3
    semesters
    2
    leftInLayer
    1
    current
    null
    phase
    "layer"
  9. 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
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,0,1,0]
    ready
    []
    removed
    [0,1,4,2]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    4
    semesters
    2
    leftInLayer
    0
    current
    2
    phase
    "remove"
  10. 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
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,0,0,0]
    ready
    [3]
    removed
    [0,1,4,2]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    4
    semesters
    2
    leftInLayer
    0
    current
    2
    phase
    "release"
    next
    3
    edgeIndex
    0
  11. Freeze the courses eligible before this semester starts.

    Only this captured number may finish now. A newly unlocked course requires its prerequisites to finish in an earlier semester.

    n
    5
    pairs
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,0,0,0]
    ready
    [3]
    removed
    [0,1,4,2]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    4
    semesters
    3
    leftInLayer
    1
    current
    null
    phase
    "layer"
  12. 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
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,0,0,0]
    ready
    []
    removed
    [0,1,4,2,3]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    5
    semesters
    3
    leftInLayer
    0
    current
    3
    phase
    "remove"
  13. 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
    [[0,2],[1,2],[2,3]]
    graph
    null
    outgoing
    [[2],[2],[3],[],[]]
    reverse
    [[],[],[],[],[]]
    remaining
    [0,0,0,0,0]
    ready
    []
    removed
    [0,1,4,2,3]
    order
    []
    safe
    [false,false,false,false,false]
    completed
    5
    semesters
    3
    leftInLayer
    0
    current
    null
    phase
    "complete"
  14. 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
    3

Repeated relations do not create extra semesters

Input: {"n":3,"pairs":[[0,1],[0,1],[1,2]]} · Minimum semesters / −1: 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.

Parallel semesters — frozen ready batches

Phase: seed.

Relations are [before, after]; both labels are zero-based.

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

  • 0

Removed vertices — teaching history

Empty.

Semester number: 0. Pops remaining in this frozen semester: 0. Completed: 0 of 3. Only the captured batch can finish now; newly released courses wait until next semester. Capacity is unlimited and every course takes one semester. A residual cycle makes the final answer −1 even after partial progress.

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
VariableValue
n3
pairs[[0,1],[0,1],[1,2]]
graphnull
outgoing[[1,1],[2],[]]
reverse[[],[],[]]
remaining[0,2,1]
ready[0]
removed[]
order[]
safe[false,false,false]
completed0
semesters0
leftInLayer0
currentnull
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 minimumSemesters(int n,int[][] relations) {
 8         validate(n,relations);List<List<Integer>> outgoing=new ArrayList<>();for(int v=0;v<n;v++)outgoing.add(new ArrayList<>());int[] indegree=new int[n];
 9         for(int[] pair:relations){outgoing.get(pair[0]).add(pair[1]);indegree[pair[1]]++;}
10         ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(indegree[v]==0)ready.addLast(v);int completed=0,semesters=0;
11         while(!ready.isEmpty()) {
12             int size=ready.size();semesters++;
13             for(int i=0;i<size;i++){int course=ready.removeFirst();completed++;for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);}
14         }
15         return completed==n?semesters:-1;
16     }
17     public static int baseline(int n,int[][] relations) {
18         validate(n,relations);boolean[] done=new boolean[n];int completed=0,semesters=0;
19         while(completed<n){boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!done[v];for(int[] pair:relations)if(!done[pair[0]])eligible[pair[1]]=false;int gained=0;for(int v=0;v<n;v++)if(eligible[v]){done[v]=true;gained++;}if(gained==0)return -1;completed+=gained;semesters++;}return semesters;
20     }
21 }
22

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

Read the full static trace
  1. 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
    [[0,1],[0,1],[1,2]]
    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"
  2. Freeze the courses eligible before this semester starts.

    Only this captured number may finish now. A newly unlocked course requires its prerequisites to finish in an earlier semester.

    n
    3
    pairs
    [[0,1],[0,1],[1,2]]
    graph
    null
    outgoing
    [[1,1],[2],[]]
    reverse
    [[],[],[]]
    remaining
    [0,2,1]
    ready
    [0]
    removed
    []
    order
    []
    safe
    [false,false,false]
    completed
    0
    semesters
    1
    leftInLayer
    1
    current
    null
    phase
    "layer"
  3. 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
    [[0,1],[0,1],[1,2]]
    graph
    null
    outgoing
    [[1,1],[2],[]]
    reverse
    [[],[],[]]
    remaining
    [0,2,1]
    ready
    []
    removed
    [0]
    order
    []
    safe
    [false,false,false]
    completed
    1
    semesters
    1
    leftInLayer
    0
    current
    0
    phase
    "remove"
  4. 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
    [[0,1],[0,1],[1,2]]
    graph
    null
    outgoing
    [[1,1],[2],[]]
    reverse
    [[],[],[]]
    remaining
    [0,1,1]
    ready
    []
    removed
    [0]
    order
    []
    safe
    [false,false,false]
    completed
    1
    semesters
    1
    leftInLayer
    0
    current
    0
    phase
    "release"
    next
    1
    edgeIndex
    0
  5. 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
    [[0,1],[0,1],[1,2]]
    graph
    null
    outgoing
    [[1,1],[2],[]]
    reverse
    [[],[],[]]
    remaining
    [0,0,1]
    ready
    [1]
    removed
    [0]
    order
    []
    safe
    [false,false,false]
    completed
    1
    semesters
    1
    leftInLayer
    0
    current
    0
    phase
    "release"
    next
    1
    edgeIndex
    1
  6. Freeze the courses eligible before this semester starts.

    Only this captured number may finish now. A newly unlocked course requires its prerequisites to finish in an earlier semester.

    n
    3
    pairs
    [[0,1],[0,1],[1,2]]
    graph
    null
    outgoing
    [[1,1],[2],[]]
    reverse
    [[],[],[]]
    remaining
    [0,0,1]
    ready
    [1]
    removed
    [0]
    order
    []
    safe
    [false,false,false]
    completed
    1
    semesters
    2
    leftInLayer
    1
    current
    null
    phase
    "layer"
  7. 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
    [[0,1],[0,1],[1,2]]
    graph
    null
    outgoing
    [[1,1],[2],[]]
    reverse
    [[],[],[]]
    remaining
    [0,0,1]
    ready
    []
    removed
    [0,1]
    order
    []
    safe
    [false,false,false]
    completed
    2
    semesters
    2
    leftInLayer
    0
    current
    1
    phase
    "remove"
  8. 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
    [[0,1],[0,1],[1,2]]
    graph
    null
    outgoing
    [[1,1],[2],[]]
    reverse
    [[],[],[]]
    remaining
    [0,0,0]
    ready
    [2]
    removed
    [0,1]
    order
    []
    safe
    [false,false,false]
    completed
    2
    semesters
    2
    leftInLayer
    0
    current
    1
    phase
    "release"
    next
    2
    edgeIndex
    0
  9. Freeze the courses eligible before this semester starts.

    Only this captured number may finish now. A newly unlocked course requires its prerequisites to finish in an earlier semester.

    n
    3
    pairs
    [[0,1],[0,1],[1,2]]
    graph
    null
    outgoing
    [[1,1],[2],[]]
    reverse
    [[],[],[]]
    remaining
    [0,0,0]
    ready
    [2]
    removed
    [0,1]
    order
    []
    safe
    [false,false,false]
    completed
    2
    semesters
    3
    leftInLayer
    1
    current
    null
    phase
    "layer"
  10. 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
    [[0,1],[0,1],[1,2]]
    graph
    null
    outgoing
    [[1,1],[2],[]]
    reverse
    [[],[],[]]
    remaining
    [0,0,0]
    ready
    []
    removed
    [0,1,2]
    order
    []
    safe
    [false,false,false]
    completed
    3
    semesters
    3
    leftInLayer
    0
    current
    2
    phase
    "remove"
  11. 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
    [[0,1],[0,1],[1,2]]
    graph
    null
    outgoing
    [[1,1],[2],[]]
    reverse
    [[],[],[]]
    remaining
    [0,0,0]
    ready
    []
    removed
    [0,1,2]
    order
    []
    safe
    [false,false,false]
    completed
    3
    semesters
    3
    leftInLayer
    0
    current
    null
    phase
    "complete"
  12. 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
    3

A partial first semester cannot bypass a cycle

Input: {"n":3,"pairs":[[0,1],[1,0]]} · Minimum semesters / −1: -1

Step 1 of 5: 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.

Parallel semesters — frozen ready batches

Phase: seed.

Relations are [before, after]; both labels are zero-based.

Vertices — counts include pending edge releases of the current removal

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

Ready FIFO — front at left; newly ready entries append

  • 2

Removed vertices — teaching history

Empty.

Semester number: 0. Pops remaining in this frozen semester: 0. Completed: 0 of 3. Only the captured batch can finish now; newly released courses wait until next semester. Capacity is unlimited and every course takes one semester. A residual cycle makes the final answer −1 even after partial progress.

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
VariableValue
n3
pairs[[0,1],[1,0]]
graphnull
outgoing[[1],[0],[]]
reverse[[],[],[]]
remaining[1,1,0]
ready[2]
removed[]
order[]
safe[false,false,false]
completed0
semesters0
leftInLayer0
currentnull
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 minimumSemesters(int n,int[][] relations) {
 8         validate(n,relations);List<List<Integer>> outgoing=new ArrayList<>();for(int v=0;v<n;v++)outgoing.add(new ArrayList<>());int[] indegree=new int[n];
 9         for(int[] pair:relations){outgoing.get(pair[0]).add(pair[1]);indegree[pair[1]]++;}
10         ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(indegree[v]==0)ready.addLast(v);int completed=0,semesters=0;
11         while(!ready.isEmpty()) {
12             int size=ready.size();semesters++;
13             for(int i=0;i<size;i++){int course=ready.removeFirst();completed++;for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);}
14         }
15         return completed==n?semesters:-1;
16     }
17     public static int baseline(int n,int[][] relations) {
18         validate(n,relations);boolean[] done=new boolean[n];int completed=0,semesters=0;
19         while(completed<n){boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!done[v];for(int[] pair:relations)if(!done[pair[0]])eligible[pair[1]]=false;int gained=0;for(int v=0;v<n;v++)if(eligible[v]){done[v]=true;gained++;}if(gained==0)return -1;completed+=gained;semesters++;}return semesters;
20     }
21 }
22

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

Read the full static trace
  1. 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
    [[0,1],[1,0]]
    graph
    null
    outgoing
    [[1],[0],[]]
    reverse
    [[],[],[]]
    remaining
    [1,1,0]
    ready
    [2]
    removed
    []
    order
    []
    safe
    [false,false,false]
    completed
    0
    semesters
    0
    leftInLayer
    0
    current
    null
    phase
    "seed"
  2. Freeze the courses eligible before this semester starts.

    Only this captured number may finish now. A newly unlocked course requires its prerequisites to finish in an earlier semester.

    n
    3
    pairs
    [[0,1],[1,0]]
    graph
    null
    outgoing
    [[1],[0],[]]
    reverse
    [[],[],[]]
    remaining
    [1,1,0]
    ready
    [2]
    removed
    []
    order
    []
    safe
    [false,false,false]
    completed
    0
    semesters
    1
    leftInLayer
    1
    current
    null
    phase
    "layer"
  3. 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
    [[0,1],[1,0]]
    graph
    null
    outgoing
    [[1],[0],[]]
    reverse
    [[],[],[]]
    remaining
    [1,1,0]
    ready
    []
    removed
    [2]
    order
    []
    safe
    [false,false,false]
    completed
    1
    semesters
    1
    leftInLayer
    0
    current
    2
    phase
    "remove"
  4. 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
    3
    pairs
    [[0,1],[1,0]]
    graph
    null
    outgoing
    [[1],[0],[]]
    reverse
    [[],[],[]]
    remaining
    [1,1,0]
    ready
    []
    removed
    [2]
    order
    []
    safe
    [false,false,false]
    completed
    1
    semesters
    1
    leftInLayer
    0
    current
    null
    phase
    "cycle"
  5. 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
    -1

Empty universe requires no semester

Input: {"n":0,"pairs":[]} · Minimum semesters / −1: 0

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.

Parallel semesters — frozen ready batches

Phase: seed.

Relations are [before, after]; both labels are zero-based.

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.

    Semester number: 0. Pops remaining in this frozen semester: 0. Completed: 0 of 0. Only the captured batch can finish now; newly released courses wait until next semester. Capacity is unlimited and every course takes one semester. A residual cycle makes the final answer −1 even after partial progress.

    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
    VariableValue
    n0
    pairs[]
    graphnull
    outgoing[]
    reverse[]
    remaining[]
    ready[]
    removed[]
    order[]
    safe[]
    completed0
    semesters0
    leftInLayer0
    currentnull
    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 minimumSemesters(int n,int[][] relations) {
 8         validate(n,relations);List<List<Integer>> outgoing=new ArrayList<>();for(int v=0;v<n;v++)outgoing.add(new ArrayList<>());int[] indegree=new int[n];
 9         for(int[] pair:relations){outgoing.get(pair[0]).add(pair[1]);indegree[pair[1]]++;}
10         ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(indegree[v]==0)ready.addLast(v);int completed=0,semesters=0;
11         while(!ready.isEmpty()) {
12             int size=ready.size();semesters++;
13             for(int i=0;i<size;i++){int course=ready.removeFirst();completed++;for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);}
14         }
15         return completed==n?semesters:-1;
16     }
17     public static int baseline(int n,int[][] relations) {
18         validate(n,relations);boolean[] done=new boolean[n];int completed=0,semesters=0;
19         while(completed<n){boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!done[v];for(int[] pair:relations)if(!done[pair[0]])eligible[pair[1]]=false;int gained=0;for(int v=0;v<n;v++)if(eligible[v]){done[v]=true;gained++;}if(gained==0)return -1;completed+=gained;semesters++;}return semesters;
20     }
21 }
22

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

    Read the full static trace
    1. 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"
    2. 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"
    3. 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

    No prerequisites means one parallel semester

    Input: {"n":4,"pairs":[]} · Minimum semesters / −1: 1

    Step 1 of 8: 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.

    Parallel semesters — frozen ready batches

    Phase: seed.

    Relations are [before, after]; both labels are zero-based.

    Vertices — counts include pending edge releases of the current removal

    • 00 incoming remainingoriginal successors: (none)
    • 10 incoming remainingoriginal successors: (none)
    • 20 incoming remainingoriginal successors: (none)
    • 30 incoming remainingoriginal successors: (none)

    Ready FIFO — front at left; newly ready entries append

    • 0
    • 1
    • 2
    • 3

    Removed vertices — teaching history

    Empty.

    Semester number: 0. Pops remaining in this frozen semester: 0. Completed: 0 of 4. Only the captured batch can finish now; newly released courses wait until next semester. Capacity is unlimited and every course takes one semester. A residual cycle makes the final answer −1 even after partial progress.

    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
    VariableValue
    n4
    pairs[]
    graphnull
    outgoing[[],[],[],[]]
    reverse[[],[],[],[]]
    remaining[0,0,0,0]
    ready[0,1,2,3]
    removed[]
    order[]
    safe[false,false,false,false]
    completed0
    semesters0
    leftInLayer0
    currentnull
    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 minimumSemesters(int n,int[][] relations) {
 8         validate(n,relations);List<List<Integer>> outgoing=new ArrayList<>();for(int v=0;v<n;v++)outgoing.add(new ArrayList<>());int[] indegree=new int[n];
 9         for(int[] pair:relations){outgoing.get(pair[0]).add(pair[1]);indegree[pair[1]]++;}
10         ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(indegree[v]==0)ready.addLast(v);int completed=0,semesters=0;
11         while(!ready.isEmpty()) {
12             int size=ready.size();semesters++;
13             for(int i=0;i<size;i++){int course=ready.removeFirst();completed++;for(int next:outgoing.get(course))if(--indegree[next]==0)ready.addLast(next);}
14         }
15         return completed==n?semesters:-1;
16     }
17     public static int baseline(int n,int[][] relations) {
18         validate(n,relations);boolean[] done=new boolean[n];int completed=0,semesters=0;
19         while(completed<n){boolean[] eligible=new boolean[n];for(int v=0;v<n;v++)eligible[v]=!done[v];for(int[] pair:relations)if(!done[pair[0]])eligible[pair[1]]=false;int gained=0;for(int v=0;v<n;v++)if(eligible[v]){done[v]=true;gained++;}if(gained==0)return -1;completed+=gained;semesters++;}return semesters;
20     }
21 }
22

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

    Read the full static trace
    1. 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
      []
      graph
      null
      outgoing
      [[],[],[],[]]
      reverse
      [[],[],[],[]]
      remaining
      [0,0,0,0]
      ready
      [0,1,2,3]
      removed
      []
      order
      []
      safe
      [false,false,false,false]
      completed
      0
      semesters
      0
      leftInLayer
      0
      current
      null
      phase
      "seed"
    2. Freeze the courses eligible before this semester starts.

      Only this captured number may finish now. A newly unlocked course requires its prerequisites to finish in an earlier semester.

      n
      4
      pairs
      []
      graph
      null
      outgoing
      [[],[],[],[]]
      reverse
      [[],[],[],[]]
      remaining
      [0,0,0,0]
      ready
      [0,1,2,3]
      removed
      []
      order
      []
      safe
      [false,false,false,false]
      completed
      0
      semesters
      1
      leftInLayer
      4
      current
      null
      phase
      "layer"
    3. 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
      []
      graph
      null
      outgoing
      [[],[],[],[]]
      reverse
      [[],[],[],[]]
      remaining
      [0,0,0,0]
      ready
      [1,2,3]
      removed
      [0]
      order
      []
      safe
      [false,false,false,false]
      completed
      1
      semesters
      1
      leftInLayer
      3
      current
      0
      phase
      "remove"
    4. 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
      []
      graph
      null
      outgoing
      [[],[],[],[]]
      reverse
      [[],[],[],[]]
      remaining
      [0,0,0,0]
      ready
      [2,3]
      removed
      [0,1]
      order
      []
      safe
      [false,false,false,false]
      completed
      2
      semesters
      1
      leftInLayer
      2
      current
      1
      phase
      "remove"
    5. 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
      []
      graph
      null
      outgoing
      [[],[],[],[]]
      reverse
      [[],[],[],[]]
      remaining
      [0,0,0,0]
      ready
      [3]
      removed
      [0,1,2]
      order
      []
      safe
      [false,false,false,false]
      completed
      3
      semesters
      1
      leftInLayer
      1
      current
      2
      phase
      "remove"
    6. 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
      []
      graph
      null
      outgoing
      [[],[],[],[]]
      reverse
      [[],[],[],[]]
      remaining
      [0,0,0,0]
      ready
      []
      removed
      [0,1,2,3]
      order
      []
      safe
      [false,false,false,false]
      completed
      4
      semesters
      1
      leftInLayer
      0
      current
      3
      phase
      "remove"
    7. 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
      4
      pairs
      []
      graph
      null
      outgoing
      [[],[],[],[]]
      reverse
      [[],[],[],[]]
      remaining
      [0,0,0,0]
      ready
      []
      removed
      [0,1,2,3]
      order
      []
      safe
      [false,false,false,false]
      completed
      4
      semesters
      1
      leftInLayer
      0
      current
      null
      phase
      "complete"
    8. 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
      1

    Test the contract

    1. Input: n=0 and no relations
      Output: 0

      There is no semester to execute.

    2. Input: Many isolated courses
      Output: 1 for nonempty n

      Unlimited capacity handles them together.

    3. Input: Diamond plus disconnected course
      Output: longest-chain count

      Parallel prerequisites finish in the same batch.

    4. Input: Cycle plus a free course
      Output: -1

      Partial elapsed rounds do not prove feasibility.

    5. Input: 100,000-course chain and duplicated relations
      Output: 100,000; duplicates add no term

      Iterative depth and occurrence-count boundaries.

    Common mistakes and counterexamples

    Drain newly appended courses in the same round

    Counterexample: 0→1→2 would incorrectly finish in one semester.

    Capture queue size once per outer iteration.

    Treat each pop as one semester

    Counterexample: Three unrelated courses need one semester, not three.

    Increment once per complete frozen batch.

    Reverse the relation format

    Counterexample: [0,1] means 0 before 1 for this API.

    Do not copy DSA-104 pair indexing without adapting the contract.

    Return partial elapsed rounds on a cycle

    Counterexample: A free course can finish while another component is cyclic.

    Return -1 whenever completed<n.

    Follow-ups

    Limit each semester to at most k courses.

    Greedily taking arbitrary ready courses can lose the optimum. For small n use a completed-subset DP/BFS that chooses eligible subsets of size at most k; larger variants require a different scope/optimization discussion.

    Give courses different positive durations.

    For a DAG, compute earliest finish[v]=duration[v]+max(finish[prerequisites]) in topological order. Frozen unit layers no longer equal elapsed time; use wide arithmetic under explicit bounds.

    Return one optimal semester assignment.

    Store the frozen batch membership or per-course earliest semester. Allocate independent output rows, preserve all labels once, and verify every edge crosses to a later row.

    Related foundations

    Keep practicing

    Return to the lesson

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