Aug 8nd, 2025
topological sort
Edit me

#. Problem

Problem link

1. My approach

The main objective was to not make a cycle in a graph, which I went for Union-find.

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    const arr = Array.from({length: numCourses}, () => -1);

    const findRoute = (arr, a) => {
        if (arr[a] == -1) return a;
        arr[a] = findRoute(arr, arr[a]);
        return arr[a];
    }

    const update = (arr, from, to) => {
        arr[to] = findRoute(arr, from)
        console.log(`from -> to : ${from} -> ${to}`);
        console.log(arr);
    }

    const isLoop = (arr, from, to) => {
        const routeFrom = findRoute(arr, from);
        return routeFrom == to;
    }

    const sorted = prerequisites.sort((a, b) => a[1] - b[1] ? a[1] - b[1] : a[0] - b[0]);

    for(const [a,b] of sorted){
        if(isLoop(arr, b, a)) return false;
        update(arr, b, a); 
    }

    return true;
};

And I realized that this has a direction, I found out that it won’t work. Also, with the prerequisites, if I go brute-force, it can be exponential, as 1 vertex can have N-1 roots, and these N-1 roots can also have N-2 roots.

2. Solution (Topological sort)

I found out this algorithm here and there, but this website was very intuitive. Basically, finding nodes with no edges directed to, and removing those. Continuing this process would give you a good view of the whole structure or prerequisites. If you cannot find any nodes that have 0 edges directed to, that means it will make a cycle, which means it cannot be done.

First approach was very straight forward with floyd-warshall

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    // const topological = [];
    let newPre = [...prerequisites];
    let isRemoved = true

    while(isRemoved && newPre.length){
        isRemoved = false;

        const followed = Array.from({length: numCourses}, () => 0);
        for(const [to, from] of newPre){
            followed[to] = 1;
        }

        for(const i in followed){
            if(!followed[i]) {
                newPre = newPre.filter(el => el[1] != i);
                isRemoved = true;
            }
        }
    }

    return newPre.length == 0;
};

And I got Time Limit Error, due to N^3. (2000^3) So I changed the code more efficient.

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    const q = [];
    const m = Array.from({length: numCourses}, () => Array.from({length: numCourses}, () => 0));
    const followedBy = Array.from({length: numCourses}, () => 0);

    // 5000
    for(const [to, from] of prerequisites){
        followedBy[to] += 1;
        m[from][to] = 1;
    }

    // 2000 
    for(const i in followedBy){
        if(!followedBy[i]) q.push(i);
    }

    // 2000 
    while(q.length){
        const v = q.shift();
        let hasDeleted = false;

        // deleting and adding to queue, 2000
        for(let i = 0; i < numCourses; i++){
            if(m[v][i] > 0){
                followedBy[i] -= 1;
                m[v][i] = 0;
                hasDeleted = true;
                if(followedBy[i] == 0) q.push(i);
            }
        }
    }

    // 2000
    return followedBy.reduce((acc, el) => acc += el, 0) == 0;
};

and as you can see it barely made it. Weird, it’s only 2000^2, but right below 1000 ms.

Time - O(n^2) Space - O(n^2)
993 ms 97.2 MB

So asked Chat GPT and got the better idea than using matrix. Matix is useless since I don’t really check regarding that, and once a node is removed, that’s basically removing 1 row and 1 column from the matrix. So traversing through the connected edges would be a better approach and faster.

Also, shift is adding another N complexity, which should not be much, but still.

So here is the final code:

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    const q = [];
    const followedBy = Array.from({length: numCourses}, () => 0);
    const following = Array.from({length: numCourses}, () => []);

    // 5000
    for(const [to, from] of prerequisites){
        followedBy[to] += 1;
        following[from].push(to);
    }

    // 2000 
    for(const i in followedBy){
        if(!followedBy[i]) q.push(i);
    }

    let ptr = 0;

    // 2000 
    while(ptr < q.length){
        const v = q[ptr];
        ptr++;

        // it's +5000, not *5000
        // because it doesn't go over the edges that were already traveled.
        for(const to of following[v]){
            followedBy[to] -= 1;
            if(followedBy[to] == 0) q.push(to);
        }
    }

    // Therefore this is O(V+E)

    // 2000
    return followedBy.reduce((acc, el) => acc += el, 0) == 0;
};
Time - O(V+E) Space - O(V+E)
19 ms 61.4 MB

3. Epilogue

What I’ve learned from this exercise:

  • Same logic can be code differently for the best optimal courses