There are a total of numCourses
courses you have to take, labeled from 0
to numCourses - 1
. You are given an array prerequisites
where prerequisites[i] = [ai, bi]
indicates that you must take course bi
first if you want to take course ai
.
[0, 1]
, indicates that to take course 0
you have to first take course 1
.Return true
if you can finish all courses. Otherwise, return false
.
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
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach to the course schedule problem involves checking every possible order in which you could take the courses. We want to see if any of these orderings allow you to complete all the courses without violating any prerequisites.
Here's how the algorithm would work step-by-step:
def can_finish_brute_force(number_of_courses, prerequisites):
import itertools
# Generate all possible course orderings
for course_ordering in itertools.permutations(range(number_of_courses)):
can_take_all_courses = True
# Check if the current ordering is valid
for course_to_take in course_ordering:
for prerequisite_course, course_needing_prerequisite in prerequisites:
if course_needing_prerequisite == course_to_take:
# Ensure prerequisite is met before taking the course
if course_needing_prerequisite in course_ordering and prerequisite_course in course_ordering:
if course_ordering.index(prerequisite_course) > course_ordering.index(course_needing_prerequisite):
can_take_all_courses = False
break
if not can_take_all_courses:
break
# If a valid ordering is found, return True
if can_take_all_courses:
return True
# If no valid ordering is found, return False
return False
The problem describes courses with dependencies, and the question is whether we can take all courses. We can solve this by figuring out the order we must take the courses. We will use a technique to identify courses with no prerequisites and iteratively build a valid schedule.
Here's how the algorithm would work step-by-step:
def can_finish(number_of_courses, prerequisites):
# Create a list to store the in-degree of each course
course_indegree = [0] * number_of_courses
# Create a list to store the adjacencies of each course
course_adjacencies = [[] for _ in range(number_of_courses)]
for course, prerequisite in prerequisites:
course_indegree[course] += 1
course_adjacencies[prerequisite].append(course)
# Queue for courses with no prerequisites.
no_prerequisites_queue = []
for course in range(number_of_courses):
if course_indegree[course] == 0:
no_prerequisites_queue.append(course)
courses_taken_count = 0
# Iteratively take courses.
while no_prerequisites_queue:
course = no_prerequisites_queue.pop(0)
courses_taken_count += 1
# Reduce the in-degree of dependent courses.
for dependent_course in course_adjacencies[course]:
course_indegree[dependent_course] -= 1
# Enqueue courses with no remaining prerequisites.
if course_indegree[dependent_course] == 0:
no_prerequisites_queue.append(dependent_course)
# If we've taken all courses, it's possible.
if courses_taken_count == number_of_courses:
return True
else:
# Cycle exists if we can't take all courses
return False
Case | How to Handle |
---|---|
numCourses is 0 or negative | Return true because there are no courses to take, thus no dependencies to violate. |
prerequisites is null or empty | Return true, as there are no dependencies, allowing all courses to be taken. |
prerequisites contains self-loops (e.g., [0, 0]) | The algorithm should detect the cycle and return false as a course cannot depend on itself. |
prerequisites represents a cyclic dependency graph | The topological sort or cycle detection algorithm should correctly identify the cycle and return false. |
Maximum sized inputs (large numCourses and prerequisites list) causing potential memory issues | The algorithm should be designed with memory efficiency in mind, possibly using adjacency lists instead of matrices. |
Inputs with a large number of courses and very few dependencies (sparse graph) | The algorithm should still execute efficiently, as it only needs to process the provided dependencies. |
Inputs with a small number of courses and dense dependencies (almost every course depends on another) | The algorithm's time complexity should handle this scenario without significant performance degradation. |
prerequisites contains duplicate entries (e.g., multiple [0, 1]) | The algorithm should treat these as a single dependency, not affecting correctness. |