Course Schedule Leetcode Problem 207 [Python Solution]

In this guide, we will explore the LeetCode problem Course Schedule, which falls under the category of Graph problems.

This problem assesses whether it is possible to complete a set of courses given certain prerequisites.

We will provide a Python solution to this problem, explain the reasoning behind our approach, and discuss the time and space complexity of the solution.

Problem Overview

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 of prerequisites, where each prerequisites[i] is a pair [ai, bi], indicating that course bi must be completed before taking course ai.

The task is to determine whether it is possible to finish all the courses.

If it is possible, return true; otherwise, return false.

Let’s illustrate this with an example:

Example 1:

Input:

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

Output: true

Explanation: There are a total of 2 courses to take.

To take course 1, you should have finished course 0. So it is possible.

Example 2:

Input:

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

Output: false

Explanation: There are a total of 2 courses to take.

To take course 1, you should have finished course 0, and to take course 0, you should also have finished course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

Now, let’s delve into the solution for this problem.

Efficient Python Code Solution

We will use Depth-First Search (DFS) to solve this problem efficiently.

The idea is to create a graph of courses and their prerequisites and then traverse this graph to check if it contains any cycles.

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Create a prerequisite map to store prerequisites for each course
        preMap = {i: [] for i in range(numCourses)}

        # Map each course to its prerequisites
        for course, prereq in prerequisites:
            preMap[course].append(prereq)

        # Set to keep track of currently visiting nodes during DFS
        visiting = set()

        # Depth-First Search function to check if courses can be completed
        def dfs(course):
            if course in visiting:
                return False  # Detected a cycle, return false
            if not preMap[course]:
                return True  # No prerequisites, course can be completed

            visiting.add(course)
            for prereq in preMap[course]:
                if not dfs(prereq):
                    return False  # A prerequisite cannot be completed

            visiting.remove(course)
            preMap[course] = []  # Mark the course as completed
            return True

        # Iterate through each course and check if it can be completed
        for course in range(numCourses):
            if not dfs(course):
                return False  # If any course cannot be completed, return false

        return True  # All courses can be completed

In this Python solution, we create a prerequisite map (preMap) to store the prerequisites for each course.

We then use Depth-First Search to check if we can complete all the courses.

The visiting set helps us detect cycles during the traversal.

Let’s analyze the code and the reasoning behind this approach.

Reasoning Behind Our Approach

1. We start by creating a preMap where each course is mapped to a list of its prerequisites.

This data structure helps us efficiently access the prerequisites for any course.

2. We define a Depth-First Search function dfs to explore the courses and their prerequisites.

This function will return False if it detects a cycle, indicating that the courses cannot be completed.

3. Within the dfs function, we handle the following cases:

• If we encounter a course that is already in the visiting set, it means we’ve detected a cycle, and we return False.
• If a course has no prerequisites (i.e., its prerequisite list is empty), we return True because it can be completed.
• For courses with prerequisites, we mark the current course as “visiting” and recursively check if all its prerequisites can be completed.

If any prerequisite cannot be completed (dfs returns False), we return False.

• After visiting all prerequisites and marking them as completed, we remove the course from the visiting set and mark it as completed by setting its prerequisite list to an empty list.

1. We iterate through each course and use the dfs function to check if it can be completed.

If any course cannot be completed, we return False.

If we successfully check all courses, we return True.

Now that we have a clear understanding of the solution, let’s discuss the time and space complexity.

#

Related Interview Questions By Company:

• Kth Largest Element In An Array LeetCode
• Simplify Path LeetCode
• Design Add And Search Words Data Structure LeetCode

Related Interview Questions By Difficulty:

• Island Perimeter LeetCode
• Count Sub Islands LeetCode
• Course Schedule II LeetCode

Related Interview Questions By Category:

• Number Of Islands LeetCode
• Longest Increasing Path In A Matrix LeetCode
• Alien Dictionary LeetCode

Time and Space Complexity

Time Complexity:

The time complexity of this solution is O(n + p), where:

• n is the number of courses (vertices).
• p is the number of prerequisites (edges).

In the worst case, we need to traverse all courses and prerequisites to detect cycles or complete the courses.

Therefore, the time complexity is linear with respect to the number of courses and prerequisites.

Space Complexity:

The space complexity is O(n + p), where:

• O(n) is the space used for the preMap, which stores prerequisites for each course.
• O(p) is the space used for the recursive call stack during the Depth-First Search.

In summary, the Depth-First Search approach efficiently solves the Course Schedule problem and has a linear time complexity with respect to the number of courses and prerequisites.

We encourage you to experiment with different test cases and explore further.

If you found this guide helpful, please like and engage for more content.

You can find the original problem statement and submit your solution on LeetCode Course Schedule.

This concludes our guide on solving the LeetCode problem Course Schedule with a Python solution.

We’ve discussed the problem, provided a detailed solution, explained the reasoning behind our approach, and analyzed the time and space complexity.

If you have any questions or suggestions, please feel free to comment, ask questions, or share this content with others.

Happy coding!