Course Schedule

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 you can take course a. Return true if it is possible to finish all the courses, otherwise false.

Example 1
Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
Take course 0, then course 1.
Example 2
Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Each course needs the other one first, so neither can start.

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

You can finish all courses exactly when the prerequisite graph has no cycle.

The idea

Topological sort (Kahn): count in-degrees, queue courses with 0, remove edges as you process; all processed ⇒ no cycle. (Or DFS with three colours.)

Target: O(V + E) time

Go function shape

func canFinish(numCourses int, prerequisites [][]int) bool

Reference solution

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

// CanFinish: Kahn's topological sort. prerequisites[i] = {course, mustTakeFirst}.
// Repeatedly take courses with no unmet prerequisites; if some are never taken, there is a cycle.
func CanFinish(numCourses int, prerequisites [][]int) bool {
	adj := make([][]int, numCourses)
	indegree := make([]int, numCourses)
	for _, p := range prerequisites {
		adj[p[1]] = append(adj[p[1]], p[0]) // edge: prerequisite -> course
		indegree[p[0]]++
	}
	queue := []int{}
	for i, d := range indegree {
		if d == 0 {
			queue = append(queue, i)
		}
	}
	taken := 0
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		taken++
		for _, next := range adj[node] {
			indegree[next]--
			if indegree[next] == 0 {
				queue = append(queue, next)
			}
		}
	}
	return taken == numCourses
}

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