Course Schedule II

Medium

The problem

There are numCourses courses numbered 0 to numCourses - 1. Each pair [a, b] in prerequisites means you must finish course b before course a. Return one order in which you can take all the courses. If it is impossible, return an empty slice.

Example 1
Input: numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 1, 2, 3]
Course 0 comes first, then 1 and 2, and 3 needs both. [0, 2, 1, 3] is also a correct answer, and any valid order is accepted.
Example 2
Input: numCourses = 2, prerequisites = [[1, 0]]
Output: [0, 1]
Example 3
Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: []
The two courses need each other, so no order works.

Limits

1 ≤ numCourses ≤ 2,000
0 ≤ len(prerequisites) ≤ 5,000
The same pair never appears twice

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Same detection as before — now record the order in which courses come out.

The idea

Kahn's algorithm and append each popped course; if fewer than n courses were output there is a cycle, return [].

Target: O(V + E) time

Go function shape

func findOrder(numCourses int, prerequisites [][]int) []int

Reference solution

Tested with go test. Try it yourself first, then compare.

// FindOrder returns one valid order to take all courses, or nil if the prerequisites contain a cycle.
// Kahn's algorithm: repeatedly take a course with no unmet prerequisites; if some courses can never be
// taken, they sit on a cycle.
func FindOrder(numCourses int, prerequisites [][]int) []int {
	after := make([][]int, numCourses) // after[a] = courses unlocked by a
	need := make([]int, numCourses)    // number of unmet prerequisites
	for _, p := range prerequisites {
		after[p[1]] = append(after[p[1]], p[0])
		need[p[0]]++
	}
	var queue, order []int
	for c, n := range need {
		if n == 0 {
			queue = append(queue, c)
		}
	}
	for len(queue) > 0 {
		c := queue[0]
		queue = queue[1:]
		order = append(order, c)
		for _, next := range after[c] {
			if need[next]--; need[next] == 0 {
				queue = append(queue, next)
			}
		}
	}
	if len(order) != numCourses {
		return nil
	}
	return order
}

Read the lesson: Graphs: BFS / DFS / Topological Sort