Course Schedule - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';
const READY_COURSE = 'ready_course', READY_COURSE_COLOR = 'lightgreen';
const TAKEN_COURSE = 'taken_course', TAKEN_COURSE_COLOR = 'green';

function visMainFunction(numCourses, inputPrerequisites) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startPartialBatch();
    makeVisVariable(numCourses).options({ label: 'numCourses' }).createVis();
    const prerequisites = new VisArray2D(...inputPrerequisites.map(arr => new VisArray(...arr)));
    const courseToDependents = VisArray.from({ length: numCourses }, () => []).options({ labelExtractionPolicy: deps => deps.join(',') });
    const numPrereqs = new VisArray(numCourses).fill(0);

    notification(`Filling the <code>courseToDependents</code> and <code>numPrereqs</code> using the input <code>prerequisites</code> (course, prereq pairs)`);
    let index = 0;
    for (const [dependent, course] of prerequisites) {
        const clearRow = highlightRow(prerequisites, index);
        notification(`Using ${makeColoredSpan(`index ${index}`, CURRENT_COLOR)} of input course, prereq pairs. Course ${course} is a prerequisite of course ${dependent}, so updating <code>courseToDependents</code> and <code>numPrereqs</code> accordingly.`);
        courseToDependents[course].push(dependent);
        courseToDependents[course] = courseToDependents[course]; // just a workaround for visualisation purposes not a part of original algorithm
        numPrereqs[dependent] += 1;
        clearRow();
        index += 1;
    }

    notification(`
        Initializing ${makeColoredSpan('readyCourses', READY_COURSE_COLOR)}  with the courses that can be taken immediately by scanning <code>numPrereqs</code>  
        for entries equal to <code>0</code> — these are the courses with no prerequisites, and are therefore ready to be taken right away.
    `);
    const readyCourses = new VisArray();
    for (let course = 0; course < numCourses; course++) {
        const vm = numPrereqs.makeVisManagerForIndex(course).addClass(CURRENT);
        if (numPrereqs[course] === 0) {
            vm.addClass(READY_COURSE);
            notification(`✅ Course ${course} has 0 prerequisites. It can be taken immediately — adding to ${makeColoredSpan('readyCourses', READY_COURSE_COLOR)}.`);
            readyCourses.push(course);
        }
        vm.removeAllClasses();
    }

    let coursesTaken = 0;
    makeVisVariable(coursesTaken).options({ label: 'coursesTaken' }).createVis();
    endBatch();

    while (readyCourses.length > 0) {
        startPartialBatch();
        const course = readyCourses.pop(); // Order doesn't matter
        const courseVm = numPrereqs.makeVisManagerForIndex(course).addClass(CURRENT);
        notification(`
            🎓 Popping and taking ${makeColoredSpan(`course ${course}`, CURRENT_COLOR)} from the <b>top of the stack</b> ${makeColoredSpan('readyCourses', READY_COURSE_COLOR)}.  
            This results in a depth-first progression among available courses.
        `);
        coursesTaken += 1;

        for (const dependent of courseToDependents[course]) {
            notification(`📉 Reducing prerequisites for course ${dependent} because ${makeColoredSpan(course, CURRENT_COLOR)} is being taken (it was one of the prerequisites of ${dependent}).`);
            numPrereqs[dependent] -= 1;

            if (numPrereqs[dependent] === 0) {
                const dependentVm = numPrereqs.makeVisManagerForIndex(dependent).addClass(READY_COURSE);
                notification(`✅ Course ${dependent} now has 0 prerequisites — pushing it to the <b>top</b> of ${makeColoredSpan('readyCourses', READY_COURSE_COLOR)}.`);
                readyCourses.push(dependent);
                dependentVm.removeClass(READY_COURSE);
            }
        }

        courseVm.removeClass(CURRENT).addClass(TAKEN_COURSE);
        endBatch();
    }

    if (coursesTaken === numCourses) {
        notification(`🏁 All ${numCourses} courses can be finished. ✅`);
        return true;
    } else {
        notification(`
            🚫 Only ${coursesTaken} out of ${numCourses} courses could be finished. 
            This indicates at least one cycle in the prerequisite graph, so not all courses can be completed. ❌
        `);
        return false;
    }
}

// --- Helpers and visuals ---
function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(READY_COURSE, { backgroundColor: READY_COURSE_COLOR });
    setClassProperties(TAKEN_COURSE, { backgroundColor: TAKEN_COURSE_COLOR });
}

function highlightRow(arr2D, rowIndex) {
    startBatch();
    const vms = arr2D[rowIndex].map((_, colIndex) => arr2D.makeVisManagerForIndexPair(rowIndex, colIndex).addClass(CURRENT));
    endBatch();
    return () => {
        startBatch();
        vms.forEach(vm => vm.removeClass(CURRENT));
        endBatch();
    };
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Visual Cues:</b>
        <ul>
            <li>
                ${makeColoredSpan('Current', CURRENT_COLOR)} — 
                highlights the course (or prerequisite pair row) currently being inspected or processed.
            </li>
            <li>
                ${makeColoredSpan('Ready course', READY_COURSE_COLOR)} — 
                marks courses whose <code>numPrereqs</code> count is <code>0</code>, meaning all prerequisites are satisfied
                and they are eligible to be pushed onto the <code>readyCourses</code> stack.
            </li>
            <li>
                ${makeColoredSpan('Taken course', TAKEN_COURSE_COLOR)} — 
                marks courses that have already been "taken" (popped from <code>readyCourses</code> and counted in
                <code>coursesTaken</code>), so they will not be processed again.
            </li>
        </ul>
    `);
}

Approach

We model courses and prerequisites as a directed graph: each pair [course, prereq] represents an edge prereq → course (you must take prereq before course). The question “Can we finish all courses?” becomes: Is this directed graph cycle-free?

🧱 Graph Representation

numPrereqs[i]: indegree-style counter — how many prerequisites are still unmet for course i.
courseToDependents[i]: adjacency list — all courses that directly depend on course i. If we “take” course i, each of its dependents has one fewer unmet prerequisite.

🎒 Initial Ready Stack

We scan all courses and collect those with numPrereqs[i] === 0 into readyCourses. These are courses that have no prerequisites and can be taken immediately.
readyCourses is used as a stack: new ready courses are pushed to the top, and we pop from the top when choosing the next course.

🔁 Processing (Indegree-Based Topological Traversal)

While readyCourses is not empty:
- Pop a course from the top (treating ready courses in a LIFO order) and mark it as taken.
- For each dependent course that listed this course as a prerequisite:
  - Decrement its numPrereqs by 1.
  - If it drops to 0, push that course onto readyCourses, since it is now ready to be taken.
We maintain a counter coursesTaken. Every time we pop a course from readyCourses, we increment this count.

🔁 Return Value

The function returns the result of coursesTaken === numCourses.

It returns true when it is possible to finish all numCourses — meaning the graph has no cycles and every course can eventually be taken.
It returns false when there exists at least one cycle in the prerequisite graph, since in that case, some courses never reach numPrereqs == 0 and therefore remain impossible to take.
The variable coursesTaken tracks how many courses have been successfully completed. If this count equals numCourses, all courses are finishable; otherwise, a cycle must exist.

🧠 Why Any Order of Ready Courses Will Yield Correct Result

At any step, every course in readyCourses has all its prerequisites already satisfied.
No matter which ready course you pick next (whether from the top of a stack, the front of a queue, or any other ready element), you never violate prerequisite rules, because each of them is currently independently eligible to be taken.
If a valid topological ordering exists (i.e., there is no cycle), repeatedly taking any available ready course will always allow us to eventually take all numCourses courses.
If there is a cycle, at least one course in that cycle will never see its numPrereqs drop to 0, so it never enters readyCourses. We then finish with coursesTaken < numCourses, which correctly signals that not all courses can be completed.
To keep the algorithm efficient, we implement readyCourses using a structure with O(1) insertion and removal at one end (a stack with push/pop, as in this implementation, or a queue). Because any order of ready-course selection is valid, we do not pay extra complexity for this choice.

🧭 DFS-Style vs BFS-Style & Relation to Kahn’s Algorithm

In this implementation, readyCourses is treated as a stack using push/pop. This gives a depth-first flavor: once a course becomes ready, we tend to follow its downstream dependents as far as possible before switching to other branches.
If we instead used readyCourses as a queue (using push/shift or similar), we would process courses in a breadth-first manner — handling all currently ready courses layer by layer. This is the classic Kahn’s Algorithm for topological sort.
Both the stack-based (DFS-style) and queue-based (BFS-style / Kahn’s) variants:
- Use the same in-degree idea (numPrereqs) and dependency lists.
- Have the same asymptotic complexity: O(N + E) time and O(N + E) space.
- Differ only in which ready node is chosen next, not in correctness.
The choice affects the shape of readyCourses during execution:
- Stack → deeper chains first (more depth-first behavior).
- Queue → level by level (more breadth-first behavior).
- In practice, choosing between a stack (DFS) or a queue (BFS) can slightly affect memory usage for readyCourses: a stack may be more efficient when the graph is deep but narrow (small maximum depth), while a queue can be preferable when the graph is shallow but wide (large maximum level width). However, this does not affect the asymptotic space complexity, which remains O(N + E) in both cases.

Time Complexity

Let N be the number of courses and E be the number of prerequisite pairs.

Building the graph structures — initializing and filling courseToDependents and numPrereqs — takes O(N + E) time when using arrays, since we allocate storage for all N courses and process each of the E prerequisite pairs once. If instead a Map were used and keys were added lazily, the initialization part would disappear, reducing this step’s cost to O(E).
Each course is added to and removed from readyCourses at most once, contributing O(N).
Each edge (prereq → course) is inspected once when the prereq is taken, which adds another O(E).

Therefore, the overall time complexity is O(N + E).

Space Complexity

Let N be the number of courses and E be the number of prerequisite pairs.

The courseToDependents structure stores up to E total dependencies across N courses, requiring O(N + E) space when implemented as an array of lists. If implemented as a Map, the cost becomes O(E) since only courses that appear as prerequisites would be the keys.
The numPrereqs array tracks one integer per course, using O(N) space.
The readyCourses and the variable coursesTaken together require at most O(N) additional space. In practice, the actual size of readyCourses depends on the graph’s structure — it is proportional to the maximum depth since we are using a stack (DFS) but would be proportional to maximum level width if we were using a queue (BFS) — but it is always bounded by O(N) in the worst case.

Therefore, the overall space complexity is O(N + E).

Input-1

Course Schedule - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

🧱 Graph Representation

🎒 Initial Ready Stack

🔁 Processing (Indegree-Based Topological Traversal)

🔁 Return Value

🧠 Why Any Order of Ready Courses Will Yield Correct Result

🧭 DFS-Style vs BFS-Style & Relation to Kahn’s Algorithm

Time Complexity

Space Complexity