TIC
The Interns Company

Course Schedule

MediumAcceptance: 44.5%
Depth-First SearchBreadth-First SearchGraphTopological Sort

Problem Statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]. Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Constraints:

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

Input Format:

  • An integer numCourses
  • A 2D array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai

Output Format:

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

Examples:

Example 1:

Input:

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

Output:

true

Explanation:

There are a total of 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 a total of 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. This is impossible.

Solutions

Depth-First Search (DFS) - Cycle Detection

Time: O(V + E) where V is the number of vertices (courses) and E is the number of edges (prerequisites)
Space: O(V + E) for the adjacency list and visited states

Create a directed graph from the prerequisites and use DFS to detect cycles.

Topological Sort (BFS) - Kahn's Algorithm

Time: O(V + E) where V is the number of vertices (courses) and E is the number of edges (prerequisites)
Space: O(V + E) for the adjacency list and indegree array

Create a directed graph and use Kahn's algorithm to perform topological sorting.

Algorithm Walkthrough

Example input:

Step-by-step execution:

  1. numCourses = 2, prerequisites = [[1,0]]
  2. Build adjacency list: graph[0] = [1], graph[1] = []
  3. DFS from course 0:
  4. - Mark course 0 as visiting
  5. - Visit its neighbor course 1
  6. - Mark course 1 as visiting
  7. - Course 1 has no neighbors, mark it as visited
  8. - Mark course 0 as visited
  9. No cycles detected, return true

Hints

Hint 1
This problem can be modeled as a directed graph where each course is a node and prerequisites are directed edges.
Hint 2
You need to detect if there is a cycle in the graph.
Hint 3
Consider using topological sort or a depth-first search (DFS) to detect cycles.

Video Tutorial

Course Schedule - Graph Cycle Detection

YouTube•Learn the Course Schedule solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the course prerequisites as a directed graph and watch the DFS or BFS algorithm detecting cycles.

Key visualization elements:

  • current node
  • visiting
  • visited
  • cycle detection

Similar Questions

Graph Valid Tree

Medium

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph. Return true if the graph is a valid tree, or false otherwise.

Asked By

AmazonFacebookGoogleMicrosoftAppleLinkedIn

Implementation Notes

This is a classic graph problem that demonstrates cycle detection in directed graphs. Both DFS and BFS (topological sort) approaches are commonly used.