Course Schedule II Leetcode Problem 210 [Python Solution]

You already know the drill, I won’t start telling you how in the world of computer science and programming, problem-solving skills are essential. Let’s solve Course Schedule II Leetcode Problem.

Whether you are a beginner or an experienced coder, it’s crucial to practice and hone your skills by tackling various coding challenges.

We will dive in and explore the problem, develop an efficient Python solution, and analyze the time and space complexity.

So, let’s get started!

Problem Overview

The Course Schedule II problem falls into the category of graph-related challenges.

The problem statement is as follows:

You are given a total of numCourses courses labeled from 0 to numCourses - 1.

Additionally, you are provided with an array prerequisites, where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

In simple terms, the pairs [ai, bi] specify that to take course ai, you must first complete course bi.

The goal is to find the ordering of courses you should take to finish all courses.

If there are multiple valid answers, you can return any of them.

If it’s impossible to finish all courses, return an empty array.

Example:

Let’s start with an example to clarify the problem:

Input:

numCourses = 2
prerequisites = [[1, 0]]

Output:

[0, 1]

In this example, there are two courses to take.

To take course 1, you should have finished course 0.

So the correct course order is [0, 1].

Understanding the Constraints

Before we delve into the solution, let’s analyze the constraints provided:

• 1 <= numCourses <= 2000: This constraint tells us the range of the number of courses.
• 0 <= prerequisites.length <= numCourses * (numCourses - 1): The number of prerequisites provided should fall within this range.
• prerequisites[i].length == 2: Each prerequisite is represented as a pair [ai, bi].
• 0 <= ai, bi < numCourses: The course indices should be within the valid range.
• ai != bi: A course cannot be a prerequisite for itself.
• All the pairs [ai, bi] are distinct: Each prerequisite pair is unique.

Now that we have a clear understanding of the problem statement and its constraints, let’s move on to the solution.

Course Schedule II LeetCode Problem Solution

To solve this problem, we’ll use a graph-based approach and apply the topological sort algorithm.

Topological sort is a common graph algorithm used to find a linear ordering of the vertices in a directed acyclic graph (DAG) that respects the partial order of the edges.

In our context, the courses represent the vertices, and the prerequisites form directed edges between them.

We’ll break down the solution into several components:

1. Building an Adjacency List

We’ll start by creating an adjacency list to represent the graph.

In this list, each course will be associated with its prerequisites.

This step involves parsing the prerequisites array and creating a data structure that allows us to easily determine which courses depend on other courses.

Here’s the Python code to build the adjacency list:

def build_adjacency_list(numCourses, prerequisites):
    # Initialize the adjacency list with empty lists for each course
    prereq = {c: [] for c in range(numCourses)}

    # Populate the adjacency list based on prerequisites
    for course, prereq_course in prerequisites:
        prereq[course].append(prereq_course)

    return prereq

2. Depth-First Search (DFS) for Topological Sort

We’ll implement a depth-first search (DFS) algorithm to traverse the graph and perform topological sorting.

The key idea is to visit each course while ensuring we don’t encounter any cycles.

In the code below, we use a recursive DFS approach:

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        def build_adjacency_list(numCourses, prerequisites):
            # Initialize the adjacency list with empty lists for each course
            prereq = {c: [] for c in range(numCourses)}

            # Populate the adjacency list based on prerequisites
            for course, prereq_course in prerequisites:
                prereq[course].append(prereq_course)

            return prereq

        def dfs(course):
            if course in cycle:
                return False
            if course in visit:
                return True

            cycle.add(course)
            for prereq in prereq_map[course]:
                if not dfs(prereq):
                    return False
            cycle.remove(course)
            visit.add(course)
            order.append(course)
            return True

        prereq_map = build_adjacency_list(numCourses, prerequisites)
        order = []
        visit, cycle = set(), set()

        for course in range(numCourses):
            if not dfs(course):
                return []

        return order  # Do not reverse the order

Let’s break down the code:

• We start by initializing an empty list order to store the course order, as well as sets visit and cycle to keep track of visited courses and detect cycles.
• The dfs function recursively explores the graph, starting from a given course.
• If the course is already in the cycle set, we have detected a cycle, so we return False.
• If the course is in the visit set, it means we have already visited it and don’t need to explore it further, so we return True.
• We add the course to the cycle set to mark it as currently visited.
• We recursively explore the prerequisites for the course.
• If we detect a cycle during the recursion, we return False.
• If the recursion reaches the end successfully, we remove the course from the cycle set, add it to the visit set, and append it to the order list.
• Finally, we call the dfs function for each course to ensure we visit all courses.

Time and Space Complexity

Now, let’s analyze the time and space complexity of our solution:

• Time Complexity: The time complexity of this solution is O(P + N), where P is the number of prerequisites (edges) and N is the number of courses (vertices).

We visit each course and its prerequisites exactly once, resulting in a linear time complexity.

• Space Complexity: The space complexity is O(P + N) as well.

We store the prerequisites in the adjacency list, which uses O(P) space.

Additionally, the sets visit and cycle can contain at most N elements.

Reasoning Behind Our Approach

Our approach uses topological sort to find a valid order of courses while handling cases where cycles are detected.

We start by building an adjacency list to represent the graph, and then we apply depth-first search (DFS) to traverse the graph and find the topological order.

By recursively exploring the graph and checking for cycles, we can ensure that the resulting course order is both valid and efficient.

Related Interview Questions By Company:

• Delete And Earn LeetCode
• Combination Sum LeetCode
• Check If Move Is Legal LeetCode

Related Interview Questions By Difficulty:

• Max Area Of Island LeetCode
• Word Ladder LeetCode
• Graph Valid Tree LeetCode

Related Interview Questions By Category:

• Course Schedule II LeetCode
• Best Time To Buy And Sell Stock II LeetCode
• Edit Distance LeetCode

Conclusion

In this blog post, we tackled the Course Schedule II problem from LeetCode, which is a graph-related challenge.

We developed an efficient Python solution using topological sort and explained the reasoning behind our approach.

It’s essential to practice solving various coding problems like this one to improve your problem-solving skills.

Whether you are a beginner or an experienced programmer, these challenges help sharpen your coding abilities.

If you found this guide helpful or have any questions, comments, or suggestions, please feel

free to comment and share your thoughts.

Coding is a journey, and we’re here to learn and grow together.

For the complete problem statement and to try the code yourself, you can find the question on LeetCode here.

Happy coding!