Leetcode diary: 207. Course Schedule [backtracking, graph]

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

This question was a good true medium level question, there is not much to complain but that I couldn't foresee the scope of the problem as much as I should, but hey we'll just keep on trying :P

The problem is that you will be given two inputs:
1.) number of courses
2.) array of two integer arrays.

the premise is this, you are looking at a course scheduler, for each course you take there may or may not have a prerequisite for the course.
you know there is a prerequisite for the course if it is mention in the array. For example:
[[1,0]] means that course 1 has prerequisite of course 0.
So it is the array is [courseId, prereqId].

Not all of the courses will have prerequisite, otherwise you cannot complete a course, so for:
[[1,0], [0,1]], this is an impossible course arrangement, so you should return false;

You should return true if you can complete all the courses fine.

There are unmentioned caveat by the problem description itself:
1.) each course can have multiple prerequisite
2.) each course can be prerequisite for many
3.) the only time you return false is if there is a cycle

Room below so you have time to think about the problem before diving deep:
.
.
.
.
.
.
.
.
.
.
By now you should realize that this is a directed graph problem.

So the first thing we should do is to make a map representation of the schedule:
1.) key is the course id
2.) value is an array of prerequisite id

once you have that you can start finding out whether there is a loop somewhere in this graph representation.

Note that the only way you can tell that you have a loop is if you start somewhere and come back to it again. So this means that we need some kind of counter that keeps track. I elected to use yet another map for this purpose.

However, this is not something I realized until I failed many submissions, the loop does not have to go back to the first course you started search.

For each search you start from, it can:
1.) diverge into multiple different paths
2.) have a loop in any of the multiple paths.
3.) each path diverged may diverge into more paths

Therefore you needed something that:
1.) returns false if there a loop immediately
2.) go into on path specifically, try to find loop, if not then go to the next path
3.) if only when all paths terminates, aka no loop, you return false

When I describe number 2 in what to do, you should realize that we need to do a backtracking technique, if the terminology did not ring a bell immediately, you should definitely google/revisit and do a couple backtracking problem. It's pretty easy though!

We have all we need to find out whether any course path leads to a loop. However, there is just one more thing. An experienced leetcoder should have the spider senses tingling that there should be performance issue since there could be many diverging and converging paths and stuffs. So yes, we'll need yet ANOTHER map to memoize the results ...

The full code is below:

var canFinish = function(numCourses, prerequisites) {
    const preqMap = prerequisites.reduce(function(map, coursePrereq) 
        {
            const [courseId, prereqId] = coursePrereq;
            map[courseId] ?
                map[courseId].push((prereqId + '')):
                map[courseId] = [(prereqId + '')];

            return map;
        }, {})

    let visited = {};
    const memo = {};

    for (let courseId of Object.keys(preqMap)) { 

        const hasLoop = preqMap[courseId].some(function(prereqId){
            visited = {[courseId]: true};
            if(memo[courseId]) return true;

            return !findLoop(prereqId)
        })

        if(hasLoop) {
            return false;
        } else {
            memo[courseId] = true;
        }
    }

    function findLoop (id) { 
        if(!preqMap[id]) return true;
        if(memo[id]) return memo[id];

        if(visited[id] ) {
            return false;
        }

        visited[id] = true;

        const answer = !preqMap[id].some(function(prepreId){
            return !findLoop(prepreId)
        })

        visited[id] = false;
        return answer;
    }

    return true;
};

note that the visited map is the traversing map that backtracks
the memo map remembers whether a given id has a loop or not and prevents re-visiting the next time.

Javascript is a little annoying with the int and string thing so I just converted everything into strings.

I elected .some so that the code terminates when there is a false value, it's kinda annoying that you have to remember the .some function itself terminates when it gets a true value, so you'd have to invert the boolean value.

The time complexity stuff is hard to get it ... maybe it's just I haven't taken a true algorithm class and went through the pain of it lol...

Let me know anything on your mind after reading through this, THANKS!