Problem Statement in English

There are numCourses courses available. You’re given a list of preqrequisites, preqrequisites that some or all courses have. Your task is to return True, if all courses can be taken, and False if not.

Approach

The plan is to make an adjacency list representing any prequisites that a course has. In order to see if a particular course can be taken, we need to see if each of the courses it depends on can be taken, if they can, we can continue processing other prerequisites, otherwise we can straight away say that this course cannot be completed, as it depends on a course that cannot be completed.

Clearly, recursion is our friend here, as we can recursively process courses that this course depends on.

An optimisation we can make, is that as we recursively process a node, and we see that it can be completed, we can mark it as having no dependencies/prequisites, that way later on, while assessing another course, if this course shows up as a dependency, then we can straight away say that it can be completed, and move on.

Solution in Python


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

        # init dependency map with empty list 
        # (list comprehension)
        dependencyMap = {i: [] for i in range(numCourses)}

        # [a,b] where b is required to take a
        for a, b in prerequisites:
            # add every course that is required to take a
            dependencyMap[a].append(b)

        # seen set to keep track of visited nodes for each course we're analyzing
        seen = set()

        # recursive function to check if there are any cycles (dfs traversal)
        def recursiveCall(key) -> bool:
            # we're coming back to a node we've already visited, so there is a cycle
            if key in seen:
                return False
            # if there are no dependencies for this course, we can take it
            if dependencyMap[key] == []:
                return True

            # mark this node as visited
            seen.add(key)

            # iterate over all the dependencies of this course
            for value in dependencyMap[key]:
                # if there are no dependencies for this course, we can take it
                if dependencyMap[value] == []:
                    # so go to next dependency
                    continue

                # if there are dependencies, check if there is a cycle recursively
                if not recursiveCall(value):
                    return False

            # this course can be taken so we mark it as having no dependencies
            dependencyMap[key] = []
            # remove this course from the visited set
            seen.discard(key)

            # this course can be taken
            return True

        # iterate over courses to check if they can be taken
        for k in dependencyMap:
            # if there is a cycle, return False,
            #  since this course can't be taken
            if not recursiveCall(k):
                return False
            
        # all courses can be taken
        return True

Complexity

  • Time: $O(n)$
    Since we process atmost $n$ courses.

  • Space: $O(n)$
    Since we can have atmost $n$ courses in the recursion stack.

Mistakes I Made

I made a whole bunch of mistakes in the implementation part, returning values from recursive calls and such. Nasty business to debug by the way. Whew.

And we are done.