Scale Engineer

Course Schedule II

Med
#0198Time: O(n^2) where n is the number of courses, due to the adjacency matrix representationSpace: O(n^2) for the adjacency matrix23 companies
Algorithms
Depth-First SearchBreadth-First SearchTopological Sort
Data structures
Graph
Companies
ByteDanceDoorDashIntuitKarat

Prompt

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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

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

 

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
  • All the pairs [ai, bi] are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses Depth First Search with an adjacency matrix to detect cycles and find the topological ordering of courses.

Algorithm

  1. Create an adjacency matrix to represent prerequisites
  2. Initialize visited and path arrays for cycle detection
  3. For each unvisited course:
    • Perform DFS traversal
    • Check for cycles
    • Add courses to result list during backtracking
  4. Convert result list to array and return

Walkthrough

In this approach, we first create an adjacency matrix to represent the course prerequisites. Then we perform DFS traversal while keeping track of visited nodes and nodes in the current path to detect cycles. If a cycle is detected, we return an empty array. Otherwise, we build the topological order during the DFS backtracking.

class Solution {    private boolean[][] adjMatrix;    private boolean[] visited;    private boolean[] path;    private List<Integer> order;        public int[] findOrder(int numCourses, int[][] prerequisites) {        // Initialize data structures        adjMatrix = new boolean[numCourses][numCourses];        visited = new boolean[numCourses];        path = new boolean[numCourses];        order = new ArrayList<>();                // Build adjacency matrix        for (int[] pre : prerequisites) {            adjMatrix[pre[0]][pre[1]] = true;        }                // Check for cycles and build topological order        for (int i = 0; i < numCourses; i++) {            if (!visited[i] && hasCycle(i)) {                return new int[0];            }        }                // Convert list to array        int[] result = new int[numCourses];        for (int i = 0; i < numCourses; i++) {            result[i] = order.get(i);        }        return result;    }        private boolean hasCycle(int course) {        if (path[course]) return true;        if (visited[course]) return false;                path[course] = true;        visited[course] = true;                for (int i = 0; i < adjMatrix.length; i++) {            if (adjMatrix[course][i] && hasCycle(i)) {                return true;            }        }                order.add(0, course);        path[course] = false;        return false;    }}

Complexity

Time

O(n^2) where n is the number of courses, due to the adjacency matrix representation

Space

O(n^2) for the adjacency matrix

Trade-offs

Pros

  • Simple to understand and implement

  • Good for dense graphs

  • Easy to modify for additional requirements

Cons

  • Higher space complexity due to adjacency matrix

  • Not efficient for sparse graphs

  • Unnecessary space usage when prerequisites are few

Solutions

public class Solution {    public int[] FindOrder(int numCourses, int[][] prerequisites) {        var g = new List < int > [numCourses];        for (int i = 0; i < numCourses; ++i) {            g[i] = new List < int > ();        }        var indeg = new int[numCourses];        foreach(var p in prerequisites) {            int a = p[0], b = p[1];            g[b].Add(a);            ++indeg[a];        }        var q = new Queue < int > ();        for (int i = 0; i < numCourses; ++i) {            if (indeg[i] == 0) {                q.Enqueue(i);            }        }        var ans = new int[numCourses];        var cnt = 0;        while (q.Count > 0) {            int i = q.Dequeue();            ans[cnt++] = i;            foreach(int j in g[i]) {                if (--indeg[j] == 0) {                    q.Enqueue(j);                }            }        }        return cnt == numCourses ? ans : new int[0];    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem