DSA-103 · DAG feasibility with indegrees

Course Schedule — Feasibility

Intermediate · Java 21 · Version 1 · editorial draft

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

Understand the problem

Determine whether all numbered courses can be completed. A pair [course,prerequisite] means the prerequisite must be finished before that course.

numCourses is 0–100,000; prerequisites is a non-null array of 0–200,000 length-two rows, with both IDs in [0,numCourses). A zero-course input has no pairs.
Duplicate pairs are permitted and treated consistently as parallel prerequisite edges. Self-dependencies make completion impossible. Isolated courses still count.
Return boolean and preserve input. The iterative reference supports deep graphs; recursive tri-color DFS is an educational baseline tested only on small graphs.

Examples

Input: numCourses=2, prerequisites=[[1,0]]
Output: true
Finish 0, then 1.
Input: numCourses=2, prerequisites=[[1,0],[0,1]]
Output: false
Each course waits for the other.
Input: numCourses=3, prerequisites=[[1,0],[1,0]]
Output: true
Both parallel edges are removed when course 0 finishes; course 2 is independent.

Before you start

Directed edges and prerequisites
Indegree accounting and directed-cycle detection

Recognize the structure

The question asks whether prerequisite constraints admit an ordering, equivalently whether the directed graph is acyclic. Undirected component detection does not answer it. Keep edge direction prerequisite→course explicit.

Try before revealing

Hint 1

Which courses can be taken before any others?

Hint 2

After taking one, which unmet counts change?

Hint 3

Repeatedly remove zero-indegree courses; success requires removing every vertex.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Tri-color depth-first cycle detection

Visit every course with states 0=unseen, 1=active, 2=finished. An edge to an active node closes a directed cycle; an edge to a finished node does not. For 0→1→0, revisiting active 0 rejects; for a diamond-shaped DAG, encountering a finished shared descendant is safe. This is O(V+E) time and O(V+E) storage including adjacency and recursion, but deep chains can overflow Java’s call stack.

Improve the baseline

Count unmet incoming edges

Build outgoing prerequisite→course lists and indegrees. Duplicate entries appear in both structures, so each increment has one matching later decrement.

Begin with every ready course

Enqueue all zero-indegree vertices, including isolated ones. Finishing a course removes each outgoing edge and may free another course.

Count processed vertices

If all V courses are removed, the constraints are feasible. If the queue empties early, remaining vertices depend on a directed cycle.

Why it is correct

Initialize

Indegree equals every course’s number of unmet prerequisite edges; the queue contains exactly zero-indegree courses.

Preserve

A dequeued course has no unmet prerequisite. Removing its outgoing edges updates remaining indegrees exactly; enqueueing at the transition to zero adds newly ready courses once.

Characterize termination

A finite acyclic nonempty directed graph has a zero-indegree vertex, so a DAG cannot leave a nonempty stuck remainder. Conversely a directed cycle can never release its first member. Therefore processed==V exactly characterizes feasibility.

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.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public final class Solution {
    private static List<List<Integer>> graph(int n, int[][] prerequisites) {
        List<List<Integer>> outgoing = new ArrayList<>();
        for (int i = 0; i < n; i++) outgoing.add(new ArrayList<>());
        for (int[] pair : prerequisites) outgoing.get(pair[1]).add(pair[0]);
        return outgoing;
    }
    public static boolean canFinish(int n, int[][] prerequisites) {
        List<List<Integer>> outgoing = graph(n, prerequisites);
        int[] indegree = new int[n];
        for (int[] pair : prerequisites) indegree[pair[0]]++;
        Deque<Integer> ready = new ArrayDeque<>();
        for (int course = 0; course < n; course++) if (indegree[course] == 0) ready.addLast(course);
        int processed = 0;
        while (!ready.isEmpty()) {
            int course = ready.removeFirst();
            processed++;
            for (int next : outgoing.get(course)) if (--indegree[next] == 0) ready.addLast(next);
        }
        return processed == n;
    }

    public static boolean baseline(int n, int[][] prerequisites) {
        List<List<Integer>> outgoing = graph(n, prerequisites);
        int[] state = new int[n];
        for (int course = 0; course < n; course++) if (state[course] == 0 && cycle(outgoing, state, course)) return false;
        return true;
    }
    private static boolean cycle(List<List<Integer>> outgoing, int[] state, int course) {
        state[course] = 1;
        for (int next : outgoing.get(course))
            if (state[next] == 1 || (state[next] == 0 && cycle(outgoing, state, next))) return true;
        state[course] = 2;
        return false;
    }
}

Read the meaningful blocks

Orient edges explicitly

pair[1] is prerequisite and pair[0] is the dependent course.

Match duplicate accounting

Do not deduplicate only adjacency or only indegree; they must represent the same edge multiset.

Include all zero-indegree IDs

Disconnected and isolated courses remain part of the requested universe.

Complexity

O(V+E) time to construct adjacency, scan all vertices, and remove every edge once, including duplicate edges. O(V+E) graph/indegree/queue storage.

The DFS baseline has the same asymptotic bound but O(V) possible recursive depth. Output is one boolean; input pair arrays are not modified.

Exact-state walkthroughs

Reveal normal and boundary traces

Parallel edges and an isolated course

Input: {"n":3,"pairs":[[1,0],[1,0]]} · Result: true

Step 1 of 5: Count all edges and enqueue every initially ready ID.

Indegrees count the unmet edge multiset, including duplicates.

Course prerequisite state

course 00 unmet edges
course 12 unmet edges
course 20 unmet edges

Highlighted courses are ready. Duplicate edges contribute separately until their prerequisite finishes.

State after this step
Variable	Value
outgoing	`[[1,1],[],[]]`
indegree	`[0,2,0]`
ready	`[0,2]`
processedCourses	`[]`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.ArrayList;
 3 import java.util.Deque;
 4 import java.util.List;
 5 
 6 public final class Solution {
 7     private static List<List<Integer>> graph(int n, int[][] prerequisites) {
 8         List<List<Integer>> outgoing = new ArrayList<>();
 9         for (int i = 0; i < n; i++) outgoing.add(new ArrayList<>());
10         for (int[] pair : prerequisites) outgoing.get(pair[1]).add(pair[0]);
11         return outgoing;
12     }
13     public static boolean canFinish(int n, int[][] prerequisites) {
14         List<List<Integer>> outgoing = graph(n, prerequisites);
15         int[] indegree = new int[n];
16         for (int[] pair : prerequisites) indegree[pair[0]]++;
17         Deque<Integer> ready = new ArrayDeque<>();
18         for (int course = 0; course < n; course++) if (indegree[course] == 0) ready.addLast(course);
19         int processed = 0;
20         while (!ready.isEmpty()) {
21             int course = ready.removeFirst();
22             processed++;
23             for (int next : outgoing.get(course)) if (--indegree[next] == 0) ready.addLast(next);
24         }
25         return processed == n;
26     }
27 
28     public static boolean baseline(int n, int[][] prerequisites) {
29         List<List<Integer>> outgoing = graph(n, prerequisites);
30         int[] state = new int[n];
31         for (int course = 0; course < n; course++) if (state[course] == 0 && cycle(outgoing, state, course)) return false;
32         return true;
33     }
34     private static boolean cycle(List<List<Integer>> outgoing, int[] state, int course) {
35         state[course] = 1;
36         for (int next : outgoing.get(course))
37             if (state[next] == 1 || (state[next] == 0 && cycle(outgoing, state, next))) return true;
38         state[course] = 2;
39         return false;
40     }
41 }
42

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

Read the full static trace

Count all edges and enqueue every initially ready ID.
Indegrees count the unmet edge multiset, including duplicates.
outgoing
[[1,1],[],[]]
indegree
[0,2,0]
ready
[0,2]
processedCourses
[]
Finish a ready course and remove all its outgoing edges.
Remaining indegrees equal edges from unprocessed courses; ready IDs have none.
course
0
indegree
[0,0,0]
ready
[2,1]
processedCourses
[0]
Finish a ready course and remove all its outgoing edges.
Remaining indegrees equal edges from unprocessed courses; ready IDs have none.
course
2
indegree
[0,0,0]
ready
[1]
processedCourses
[0,2]
Finish a ready course and remove all its outgoing edges.
Remaining indegrees equal edges from unprocessed courses; ready IDs have none.
course
1
indegree
[0,0,0]
ready
[]
processedCourses
[0,2,1]
Return the contract result.
The final state satisfies the requested output contract.
result
true

No initial ready vertex

Input: {"n":2,"pairs":[[1,0],[0,1]]} · Result: false

Step 1 of 2: Count all edges and enqueue every initially ready ID.

Indegrees count the unmet edge multiset, including duplicates.

Course prerequisite state

course 01 unmet edges
course 11 unmet edges

Highlighted courses are ready. Duplicate edges contribute separately until their prerequisite finishes.

State after this step
Variable	Value
outgoing	`[[1],[0]]`
indegree	`[1,1]`
ready	`[]`
processedCourses	`[]`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.ArrayList;
 3 import java.util.Deque;
 4 import java.util.List;
 5 
 6 public final class Solution {
 7     private static List<List<Integer>> graph(int n, int[][] prerequisites) {
 8         List<List<Integer>> outgoing = new ArrayList<>();
 9         for (int i = 0; i < n; i++) outgoing.add(new ArrayList<>());
10         for (int[] pair : prerequisites) outgoing.get(pair[1]).add(pair[0]);
11         return outgoing;
12     }
13     public static boolean canFinish(int n, int[][] prerequisites) {
14         List<List<Integer>> outgoing = graph(n, prerequisites);
15         int[] indegree = new int[n];
16         for (int[] pair : prerequisites) indegree[pair[0]]++;
17         Deque<Integer> ready = new ArrayDeque<>();
18         for (int course = 0; course < n; course++) if (indegree[course] == 0) ready.addLast(course);
19         int processed = 0;
20         while (!ready.isEmpty()) {
21             int course = ready.removeFirst();
22             processed++;
23             for (int next : outgoing.get(course)) if (--indegree[next] == 0) ready.addLast(next);
24         }
25         return processed == n;
26     }
27 
28     public static boolean baseline(int n, int[][] prerequisites) {
29         List<List<Integer>> outgoing = graph(n, prerequisites);
30         int[] state = new int[n];
31         for (int course = 0; course < n; course++) if (state[course] == 0 && cycle(outgoing, state, course)) return false;
32         return true;
33     }
34     private static boolean cycle(List<List<Integer>> outgoing, int[] state, int course) {
35         state[course] = 1;
36         for (int next : outgoing.get(course))
37             if (state[next] == 1 || (state[next] == 0 && cycle(outgoing, state, next))) return true;
38         state[course] = 2;
39         return false;
40     }
41 }
42

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

Read the full static trace

Count all edges and enqueue every initially ready ID.
Indegrees count the unmet edge multiset, including duplicates.
outgoing
[[1],[0]]
indegree
[1,1]
ready
[]
processedCourses
[]
Return the contract result.
The final state satisfies the requested output contract.
result
false

Test the contract

Input: numCourses=0, prerequisites=[]
Output: true
Empty universe.
Input: numCourses=3, prerequisites=[]
Output: true
All isolated.
Input: numCourses=1, prerequisites=[[0,0]]
Output: false
Self-loop.
Input: numCourses=4, prerequisites=[[1,0],[2,3],[3,2]]
Output: false
A cycle in another component.

Common mistakes and counterexamples

Use one visited bit for directed cycles

Counterexample: A diamond DAG revisits a shared descendant without a cycle.

DFS needs active versus finished states, or use indegree removal.

Ignore isolated courses

Counterexample: Three courses with no pairs are feasible and all three must be considered.

Allocate and scan the full ID universe.

Deduplicate one structure only

Counterexample: [[1,0],[1,0]] can leave a false positive indegree.

Keep increments and decrements consistent.

Return true if any course was processed

Counterexample: An isolated course can coexist with another component’s cycle.

Require processed==numCourses.

Follow-ups

Return a valid course order.

Append each dequeued ID to an order list. Check every prerequisite appears earlier; compare by constraints rather than one arbitrary expected order.

Find an actual cycle.

Use a DFS parent/active stack, or analyze the blocked remainder and reconstruct a cycle. The Kahn count proves a cycle exists but is not itself a cycle witness.

Return the minimum parallel semesters.

For unit-duration courses with unlimited parallelism, process ready vertices by layers or compute longest prerequisite-path length. Resource limits or variable durations change the scheduling model.

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 · 118/20,000 characters

Self-review

I state edge direction.I account consistently for duplicates and isolated IDs.I can prove why a stuck remainder contains a cycle.

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

Related foundations

Topological reasoning: remove satisfied prerequisites

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-14 · Original explanations, examples, and Java implementations for AceYourInterviews. Familiar task names identify standard algorithmic problems; no company-frequency claims are made.