Command Palette

Search for a command to run...

Hectal
Problem 24.1 · Topological SortMedium

Course Schedule II

PatternTopological SortTop K with a Heap

What it teaches: Produce the order, not just yes or no. Here the smallest available course is always taken, so the answer is unique.

Practise it on judges as “Course Schedule II”.

The problem

There are numCourses courses; [a, b] means b must come before a. Return an order in which to take all courses, or [] if impossible. Whenever several courses are available, take the one with the smallest number (this makes the answer unique; the original problem accepts any valid order).

Example 1

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

Constraints

  • 1 ≤ numCourses ≤ 2000

Pattern clues in the wording

  • → Order with dependencies
  • → Smallest first among ties

These clues point to Topological Sort: Order the nodes of a directed graph so every edge goes from earlier to later, by repeatedly taking nodes with no remaining prerequisites.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        return new int[0];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
numCourses = 2
prerequisites = [[1,0]]
[0,1]
2
numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
[0,1,2,3]
3
numCourses = 3
prerequisites = [[0,2]]
[1,2,0]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Kahn's with a min-heap · O(V log V + E)
1

Kahn's with a min-heap

Time O(V log V + E) Space O(V + E)

In-degrees, a PriorityQueue of ready courses, and an output array. Return [] if fewer than n courses are output.

Approach 1
import java.util.*;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) { adj.get(p[1]).add(p[0]); indeg[p[0]]++; }
        PriorityQueue<Integer> ready = new PriorityQueue<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) ready.offer(i);
        int[] order = new int[numCourses];
        int k = 0;
        while (!ready.isEmpty()) {
            int u = ready.poll();
            order[k++] = u;
            for (int v : adj.get(u)) if (--indeg[v] == 0) ready.offer(v);
        }
        return k == numCourses ? order : new int[0];
    }
}

Verdict: A plain queue gives a valid order in O(V + E) when any order is accepted.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No prerequisites (0, 1, …, n − 1)
  • Cycle ([])

Mistakes people make

  • Returning a partial order when there's a cycle.

Interview

Follow-up questions

What if each course also had a duration and unlimited parallelism?