MEDIUM NC#87 Blind #28 Graphs / Topological Sort

207. Course Schedule

📖 Problem

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.

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •Recursive stack flow
  • •Cycle prevention
  • •Post-order reasoning

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply DFS reasoning pattern
  • •Apply Topological Sort reasoning pattern

💡 Approach

  • → Build directed graph of prerequisite relationships
  • → Detect if there's a cycle in the graph
  • → Cycle means courses cannot be completed
  • → Use DFS with visited states (0=unvisited, 1=visiting, 2=visited)
  • → Time: O(V + E), Space: O(V + E)

🛠️ Hints & Pitfalls

Hints

  • •Build directed graph of prerequisite relationships
  • •Detect if there's a cycle in the graph
  • •Cycle means courses cannot be completed

Common Pitfalls

  • •Use DFS with visited states (0=unvisited, 1=visiting, 2=visited)
  • •Time: O(V + E), Space: O(V + E)

🧪 Test Cases

Hidden tests on submit: 1

Test Case 1
Not run
Input:
canFinish(2, [[1,0]]);
Expected:
true
Test Case 2
Not run
Input:
canFinish(2, [[1,0],[0,1]]);
Expected:
false
Test Case 3
Not run
Input:
canFinish(5, [[0,1],[1,2],[2,3],[3,4]]);
Expected:
true

📝 Code Editor

📚 Reference Solution

▼
⌘K Search ⌘↩ Run ⌘S Submit