How do you approach Course Schedule?

This is a graph problem - detect if there's a cycle in a directed graph.

What is the time complexity of Course Schedule?

Time complexity: O(V + E). Space complexity: O(V + E).

What are common mistakes on Course Schedule?

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question. Building the edges the wrong way round - prerequisite pairs are the classic reversal. Seeding the queue with every node instead of only those with zero indegree.

Sitelet https://gitgood.dev/coding/course-schedule

gitGood.dev

← Back to problems

Course Schedule

MediumData Structures

Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Explanation: There are 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false

Explanation: There are 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints

- 1 <= numCourses <= 2000 - 0 <= prerequisites.length <= 5000 - prerequisites[i].length == 2 - 0 <= ai, bi < numCourses - All the pairs prerequisites[i] are unique.

Course Schedule: approach, complexity and pitfalls

A medium topological sort problem, graded against 6 test cases (3 of them hidden).

The pattern: Topological Sort

Ordering a directed acyclic graph so every dependency comes first.

Reach for it when you see: Prerequisites, build order, task scheduling, or "can this be completed?"

If you are stuck

Show the 3-step hint ladder

This is a graph problem - detect if there's a cycle in a directed graph.
Use DFS with three states: unvisited, visiting, visited.
If you encounter a 'visiting' node during DFS, there's a cycle.

The optimal approach

Show the approach: DFS Cycle Detection

Build an adjacency list. Use DFS with three states (unvisited, visiting, visited) to detect cycles. If a cycle exists, courses cannot be completed.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Topological Sort mistakes

These apply to the pattern as a whole, not just this problem.

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question.
Building the edges the wrong way round - prerequisite pairs are the classic reversal.
Seeding the queue with every node instead of only those with zero indegree.