Course Schedule II
Medium
2 views
Topics:
GraphsArrays
You are given numCourses courses labeled from 0 to numCourses - 1. You are also given an array prerequisites where prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>] indicates that you must take course b<sub>i</sub> first if you want to take course a<sub>i</sub>.
For example: The pair [0, 1] indicates that to take course 0 you have to first take course 1.
Your task: Write a function that returns the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
Example 3:
Input: numCourses = 1, prerequisites = []
Output: [0]
Constraints:
1 <= numCourses <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 20 <= a<sub>i</sub>, b<sub>i</sub> < numCoursesa<sub>i</sub> != b<sub>i</sub>- All the pairs
[a<sub>i</sub>, b<sub>i</sub>]are distinct.
Can you provide an efficient solution to determine the correct course order, considering potential cycles in the prerequisites?
Solution
Clarifying Questions
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:
- What is the valid range for numCourses and the length of the prerequisites array?
- Can there be cycles in the prerequisites? If so, should I return an empty array?
- If multiple valid course orderings exist, is any valid ordering acceptable, or is there a specific one I should prioritize?
- Can a course have no prerequisites?
- Can there be duplicate entries in the prerequisites array, and if so, how should they be handled?
Brute Force Solution
Approach
Imagine you have a list of courses where some courses need to be taken before others. The brute force method is like trying every possible order of courses to see if it works, ensuring you always take prerequisite courses first. If we find a valid order after trying all the possibilities, that's our schedule.
Here's how the algorithm would work step-by-step:
- Start by considering all possible orders in which you can take the courses.
- For each possible order, go through the list of course dependencies.
- Check if you're trying to take a course before you've taken its prerequisite. If you are, this order is invalid, and you discard it.
- If you've checked all dependencies for a particular order and none of them are violated, then this order represents a valid course schedule.
- If after checking all possible orders you find a valid course schedule, that's your answer. If not, there's no possible schedule.
Code Implementation
def find_course_schedule(number_of_courses, prerequisites):
import itertools
all_courses = list(range(number_of_courses))
# Generate all possible course orders
for possible_order in itertools.permutations(all_courses):
is_valid = True
# Check if the current order satisfies prerequisites
for course, prerequisite in prerequisites:
try:
course_index = possible_order.index(course)
prerequisite_index = possible_order.index(prerequisite)
except ValueError:
is_valid = False
break
#A course cannot be taken before its prerequisite.
if course_index < prerequisite_index:
is_valid = False
break
#If the order is valid, return the schedule.
if is_valid:
return list(possible_order)
#If no valid order is found, return an empty list.
return []Big(O) Analysis
Time Complexity
O(n! * m) – The algorithm considers all possible orderings of the n courses, which is n! (n factorial). For each of these orderings, it iterates through the m prerequisites to validate if the ordering is valid. Therefore, in the worst-case scenario, we need to check all m prerequisites for each of the n! permutations. Thus, the total number of operations is proportional to n! multiplied by m. As n! dominates m, the overall time complexity is O(n! * m).
Space Complexity
O(N!) – The described brute force approach explores all possible orderings of the N courses. This implies generating and storing these permutations, either explicitly or implicitly through recursion. The number of permutations for N items is N! (N factorial). Storing or generating each of these permutations requires space proportional to the length of the permutation, which is N. Therefore, the space complexity is O(N!).
Optimal Solution
Approach
The goal is to find a valid order to take courses, respecting prerequisites. We solve this by thinking about course dependencies and only listing courses that have no remaining prerequisites. The method focuses on systematically removing courses from the dependency graph as we add them to our order.
Here's how the algorithm would work step-by-step:
- First, figure out how many prerequisites each course has.
- Create a list of courses that have no prerequisites at all (courses you can take right away).
- Pick a course from your list of courses with no prerequisites and add it to your course schedule.
- For every other course that had the course you just scheduled as a prerequisite, reduce its prerequisite count by one (because you've now satisfied that prerequisite).
- If, after reducing a course's prerequisite count, it drops to zero, add that course to your list of courses with no prerequisites.
- Keep doing this – adding courses to your schedule and updating the prerequisite counts of other courses – until you've added all the courses or you run out of courses with no prerequisites.
- If you were able to add all courses to the schedule, then great, you found a valid order. If not, it means there's a cycle of prerequisites, and it's impossible to finish all the courses.
Code Implementation
def find_order(number_of_courses, prerequisites):
course_prerequisites_count = [0] * number_of_courses
adjacency_list = [[] for _ in range(number_of_courses)]
for course, prerequisite in prerequisites:
course_prerequisites_count[course] += 1
adjacency_list[prerequisite].append(course)
# Initialize list with courses that have no prerequisites.
no_prerequisites_courses = [
course for course in range(number_of_courses)
if course_prerequisites_count[course] == 0
]
course_schedule = []
courses_completed = 0
while no_prerequisites_courses:
# Get a course with no remaining prerequisites.
course = no_prerequisites_courses.pop(0)
course_schedule.append(course)
courses_completed += 1
# Update the prerequisite count of dependent courses.
for dependent_course in adjacency_list[course]:
course_prerequisites_count[dependent_course] -= 1
# Add to the no_prerequisites list if count is 0.
if course_prerequisites_count[dependent_course] == 0:
no_prerequisites_courses.append(dependent_course)
# If all courses were completed, return the schedule.
if courses_completed == number_of_courses:
return course_schedule
# Otherwise, there is a cycle, return an empty list.
else:
return []Big(O) Analysis
Time Complexity
O(V + E) – The algorithm initializes a degree count for each course (vertex), which takes O(V) time. The adjacency list is traversed to populate these counts, taking O(E) time where E represents the number of prerequisites (edges). The main loop processes each course (vertex) and its prerequisites (edges). Therefore, visiting each node and edge results in a total time complexity of O(V + E).
Space Complexity
O(N + P) – The algorithm uses auxiliary space to store prerequisite counts for each course, requiring an array of size N where N is the number of courses. It also maintains a queue or list of courses with no prerequisites. In the worst case, the size of this list could also grow up to N if there are no prerequisites initially. Furthermore, we also need to consider the space for storing the input prerequisites list. Let's denote the number of prerequisites by P. In graph terms, this represents the number of edges in the graph. Therefore, the total auxiliary space complexity is O(N + P).
Edge Cases
| Case | How to Handle |
|---|---|
| numCourses is 0 or negative | Return an empty array as no courses can be taken. |
| prerequisites is null or empty | Return a list containing all courses from 0 to numCourses-1 since there are no dependencies. |
| prerequisites contains a cycle (impossible to finish all courses) | Topological sort detects cycles and returns an empty array if one is found. |
| numCourses is very large (e.g., 10000) and prerequisites is relatively small | Adjacency list representation of the graph avoids unnecessary iterations and makes the solution scalable. |
| prerequisites contains duplicate entries (e.g., [1, 0] and [1, 0]) | The adjacency list and indegree calculation will simply be updated redundantly, but the correctness will not be affected. |
| A course has no prerequisites | These courses will have an indegree of 0 and will be added to the queue for processing. |
| All courses depend on each other in a single chain | Topological sort correctly handles this linear dependency and produces the correct ordering. |
| Integer overflow when calculating indegree for a very large number of prerequisites pointing to a single course | The indegree count uses integers, but the problem constraints limit the number of courses, preventing integer overflow. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
