DSA

Course Schedule - I

Covers: DFS, BFS - TOPOLOGICAL. Optimal — Time O(N+E), Space O(N).

August 8, 2026

DSA Graphs BFS DFS LeetCode Practice 🏢 Amazon 🏢 Google

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.

Practice Link

DFS APPROACH#

The key insight is that being able to finish all courses is equivalent to the prerequisite graph having no cycle — a cycle means two courses each depend on the other, making completion impossible. DFS detects cycles by tracking nodes currently on the active recursion path in coursesToDo[]; if we reach a node that is already on the current path, we have found a back edge and therefore a cycle. A separate coursesDone[] array memoises already-verified safe nodes so each node is fully processed at most once, keeping the total work linear in vertices plus edges.

Time Complexity - O(N+E), where V is the total number of courses, E is the edges (dependencies)

Space Complexity - O(N) + O(N)

The coursesToDo[] array simulates the recursion stack
Re-visiting a node on the same recursion path means a back edge → cycle
coursesDone[] helps skip already checked safe nodes to optimize performance

cpp

class Solution {
public:
    bool checkDFS(vector<vector<int>> &adj, vector<int> &coursesDone, vector<int> &coursesToDo,int currCourse)
    {
        coursesDone[currCourse]=true;
        coursesToDo[currCourse]=true;
        for(auto nextCourse: adj[currCourse])
        {
            if(coursesToDo[nextCourse])
                return true;
            else if(!coursesDone[nextCourse])
                if(checkDFS(adj, coursesDone, coursesToDo, nextCourse))
                    return true;

        }

        coursesToDo[currCourse]=false;
        return false;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        vector<vector<int>> adj(numCourses);
        for(int i=0;i<prerequisites.size();i++)
        {
            int ai = prerequisites[i][0];
            int bi = prerequisites[i][1];
            // bi -> ai
            adj[bi].push_back(ai);
        }

        vector<int> coursesDone(numCourses, false);
        vector<int> coursesToDo(numCourses, false);
        for(int i=0;i<numCourses;i++)
        {
            if(!coursesDone[i] && checkDFS(adj, coursesDone, coursesToDo,i))
                return false;
        }
        return true;

    }
};

Time Complexity: O(N+E), where V is the total number of courses, E is the edges (dependencies)

Space Complexity: O(N) + O(N)

BFS - TOPOLOGICAL APPROACH#

Kahn's algorithm approaches cycle detection from a different angle: repeatedly remove nodes with no prerequisites (in-degree zero) from the graph and decrement the in-degree of their dependents. If every course can eventually be removed this way (i.e., coursesDone == numCourses), the graph is acyclic and all courses can be finished; if any courses remain with non-zero in-degree, they are caught in a cycle. Compared to DFS, this BFS approach is often easier to reason about iteratively and avoids recursion-stack overhead — both methods share the same O(N+E) time and O(N) space complexity.

cpp

class Solution {
public:

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        vector<vector<int>> adjList(numCourses);
        for(int i=0;i<prerequisites.size();i++)
        {
            int ai = prerequisites[i][0];
            int bi = prerequisites[i][1];
            // bi -> ai
            adjList[bi].push_back(ai);
        }

        vector<int> inDegree(numCourses);
        for(int i=0;i<adjList.size();i++)
        {
            for(int j=0;j<adjList[i].size();j++)
            {
                inDegree[adjList[i][j]]++;
            }
        }

        queue<int> q;
        for(int i=0;i<inDegree.size();i++)
        {
            if(inDegree[i]==0)
                q.push(i);
        }

        int coursesDone = 0;
        while(!q.empty())
        {
            int currNode = q.front();
            q.pop();
            coursesDone++;

            for(auto nextNode: adjList[currNode])
            {
                inDegree[nextNode]--;
                if(inDegree[nextNode]==0)
                    q.push(nextNode);
            }
        }
        return coursesDone == numCourses;
    }
};

Time Complexity: O(N+E), where V is the total number of courses, E is the edges (dependencies)

Space Complexity: O(N) + O(N)

Summary#

Approach	Strategy	Time	Space	Handles Cycles?	Suitable for
BFS Topo Sort (Kahn’s)	Indegree-based	O(V+E)	O(V+E)	✅ Yes	Course ordering, No cycle detection
DFS with Recursion Stack	DFS	O(V+E)	O(V)	✅ Yes	Cycle detection

DSAMax Area of IslandDFS flood-fill to find the largest connected island. Time O(m×n), Space O(m×n).DSANumber of Ways to Arrive at DestinationGraphs. Time O(m log n), Space O(m+n).DSAWord SearchDFS - Backtracking approach. Optimal — Time O(mn * 4^L), Space O(1).

DFS APPROACH#

BFS - TOPOLOGICAL APPROACH#

Summary#

Related articles