2 min read Algorithm Coding

Neetcode - Course Schedule

Neetcode - Course Schedule
Photo by Changbok Ko / Unsplash
Code is communication.

Course Schedule

You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.

The pair [0, 1], indicates that must take course 1 before taking course 0.

There are a total of numCourses courses you are required to take, labeled from 0 to numCourses - 1. 

Return true if it is possible to finish all courses, otherwise return false.

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

Output: true

Explanation: First take course 1 (no prerequisites) and then take course 0.

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

Output: false

Explanation: In order to take course 1 you must take course 0, and to take course 0 you must take course 1. So it is impossible.

This question is trickier than previous graph problems like Neetcode - Pacific Atlantic Water Flow and Neetcode - Clone Graph . The key insight here is the need to track three distinct states in the visited array. Let’s dive into the code to understand this better.

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> visited(numCourses, 0);
        vector<vector<int>> graph(numCourses);

        for (auto& pre: prerequisites) {
            graph[pre[1]].push_back(pre[0]);
        }

        for (int i = 0; i < numCourses; ++i) {
            if (dfs(i, graph, visited)) {
                return false;
            }
        }

        return true;
    }

    bool dfs(int node, vector<vector<int>>& graph, vector<int>& visited) {
        if (visited[node] == 1) return true;
        if (visited[node] == 2) return false;

        visited[node] = 1;
        for (int neighbor : graph[node]) {
            if (dfs(neighbor, graph, visited)) {
                return true;
            }
        }

        visited[node] = 2;
        return false;
    }
};

DFS - CSY

First, we create two arrays: one is a one-dimensional array to track the state of each node, and the other is a two-dimensional array that stores the neighbors of each node.
The key part is the recursive DFS function. In this function, nodes marked with state 1 indicate they are currently being visited (i.e., part of the current traversal path), which helps detect cycles. Nodes marked with state 2 indicate they have been fully traversed with no cycles found along that path. When a node is visited for the first time, it is marked as state 1 (visiting), and then the DFS proceeds recursively to traverse all its neighbors. For example:

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

Start

  • DFS at Course 0 → visited[0] = 1 (visiting)
  • DFS Course 1 → visited[1] = 1 (visiting)
  • DFS Course 2 → visited[2] = 1 (visiting)
  • DFS Course 3 → visited[3] = 1 (visiting)

Backtrack

  • No children → visited[3] = 2 (done)
  • Back to Course 2 → visited[2] = 2 (done)
  • Back to Course 1 → visited[1] = 2 (done)
  • Back to Course 0 → visited[0] = 2 (done)

After constructing the graph as an adjacency list (or array), we begin traversing from course 0 through to course numCourses - 1. During this traversal, we perform backtracking to detect if any course is involved in a cycle with other courses. That's it.

CSY

CSY

Nagoya, Japan