Skip to content
Katabench
Try free

Course Schedule

Medium About 20 min Free, no account needed

Can every course be finished, or do the prerequisites form a cycle?

The brief

There are numCourses courses; prerequisites[i] = [a, b] means course b must be taken before course a. Return true when every course can be finished, i.e. the prerequisite graph has no cycle.

The performance bar

The obvious approach walks the dependency chain from every course by rescanning the whole edge list at every step, O(V * E * depth). The hidden test is a 2,000-course chain, which times it out. You need to detect a cycle without rescanning the edge list at every step; an O(V + E) solution clears the bar.

Starter code

C#
using System;

public class Solution
{
    // TODO: return true when the prerequisite graph has no cycle.
    public bool CanFinish(int numCourses, int[][] prerequisites)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Topological sort
Order a dependency graph and detect when its prerequisites form a cycle.

Related katas