Course Schedule II

Medium

Intuit

1 view

Topics:

GraphsDynamic Programming

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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return 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 <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
a_i != b_i
All the pairs [a_i, b_i] are distinct.

Course Schedule II

Medium

Intuit

1 view

Topics:

GraphsDynamic Programming

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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return 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 <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
a_i != b_i
All the pairs [a_i, b_i] are distinct.

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 range for `numCourses` and the number of prerequisites? Is there a maximum value I should consider?
Can there be circular dependencies in the prerequisites? For example, can course A depend on course B, and course B depend on course A?
If there are multiple valid course orderings, is any valid ordering acceptable, or is there a specific ordering you're looking for?
If it's impossible to finish all courses due to circular dependencies, should I return an empty array or is there another specific error indicator?
Can a course have no prerequisites? Can a course be a prerequisite for itself?

Brute Force Solution

Approach

Imagine you have a list of courses, and some courses must be taken before others. The brute force approach tries out every possible order you could take the courses in, checking if that order respects all the prerequisites.

Here's how the algorithm would work step-by-step:

Start by listing all possible orderings of the courses.
For each ordering, go through each course and check if its prerequisites have already been taken.
If all prerequisites for every course in the ordering are satisfied, then this ordering is a valid schedule.
Collect all the valid schedules.
If there are any valid schedules, return one of them. If none of the schedules are valid, it means it is not possible to finish all courses.

Code Implementation

def find_order_brute_force(number_of_courses, prerequisites):
    import itertools

    all_courses = list(range(number_of_courses))
    all_possible_orders = list(itertools.permutations(all_courses))

    valid_schedules = []

    for possible_order in all_possible_orders:
        is_valid = True

        # Check if the current order satisfies all prerequisites.
        for course, prerequisite_list in prerequisites.items():
            for prerequisite in prerequisite_list:
                if possible_order.index(course) < possible_order.index(prerequisite):
                    is_valid = False
                    break
            if not is_valid:
                break

        # If the order is valid, add it to the list of valid schedules.
        if is_valid:
            valid_schedules.append(list(possible_order))

    # Return a valid schedule if one exists, otherwise return an empty list.
    if valid_schedules:
        return valid_schedules[0]
    else:
        return []

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n! * n * p) – The algorithm first generates all possible orderings of the n courses. There are n! (n factorial) such orderings. For each ordering, the algorithm iterates through the courses (n courses). For each course, it checks its prerequisites. Let's denote the maximum number of prerequisites for any given course as p. Therefore, checking prerequisites for a single course in a specific order takes O(p) time. Thus, for each ordering, the prerequisite checking will take O(n * p) time. Multiplying this by the number of orderings gives a total runtime complexity of O(n! * n * p). Since factorial grows faster than any polynomial term and p is typically treated as a constant or is upper bounded, the n! term dominates.

Space Complexity

O(N!) – The brute force approach generates all possible orderings of the courses. Generating all permutations of N courses requires storing a list of all N! possible orderings. Each ordering has a length of N, contributing to a space complexity of N * N! However, the space used to store the list of orderings dominates the space needed for each individual schedule. Therefore, the auxiliary space complexity is O(N!).

Optimal Solution

Approach

The problem involves figuring out the correct order to take courses, considering some courses have prerequisites. We use a method that systematically works backward from courses with no prerequisites to build the course schedule. This ensures we only add courses to the schedule after all their prerequisite courses have been added.

Here's how the algorithm would work step-by-step:

First, identify all courses that don't have any prerequisites. These are your starting points; you can take them immediately.
Next, begin building the schedule by adding these initial courses.
As you add courses, check if any of the remaining courses now have all their prerequisites fulfilled.
If a course's prerequisites are met, add it to the schedule.
Keep repeating the process of checking for courses whose prerequisites are met and adding them to the schedule until you have either added all the courses or you find a situation where you can't add any more courses but haven't added all of them.
If you manage to add all the courses, the schedule you built is a valid course order. If you are unable to add all courses it means a valid order is not possible and an empty list should be returned.

Code Implementation

def find_order(number_of_courses, prerequisites):
    in_degree = [0] * number_of_courses
    adjacency_list = [[] for _ in range(number_of_courses)]

    for course, prerequisite in prerequisites:
        in_degree[course] += 1
        adjacency_list[prerequisite].append(course)

    course_order = []
    queue = []

    # Start with courses having no prerequisites
    for course in range(number_of_courses):
        if in_degree[course] == 0:
            queue.append(course)

    while queue:
        course = queue.pop(0)
        course_order.append(course)

        # Reduce in-degree of dependent courses
        for dependent_course in adjacency_list[course]:
            in_degree[dependent_course] -= 1
            # Add course to queue if no more prerequisites
            if in_degree[dependent_course] == 0:
                queue.append(dependent_course)

    # Detect cycle: Not all courses can be taken
    if len(course_order) != number_of_courses:
        return []

    return course_order

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(V+E) – The algorithm involves visiting each course (vertex V) to determine if its prerequisites are met. For each course, we potentially iterate through its prerequisites (edges E) to update the in-degree counts. The initial identification of courses with no prerequisites requires checking the prerequisites of all courses, which can be considered a traversal of all edges. After that, we visit each course and potentially iterate through the adjacency list. Therefore, the overall time complexity is driven by visiting all vertices and edges, resulting in O(V+E).

Space Complexity

–

Edge Cases

Case	How to Handle
numCourses is 0 or negative	Return an empty list, as no courses need to be taken.
prerequisites is null or empty	Return a list of courses from 0 to numCourses-1 in any order, as no dependencies exist.
prerequisites contains a self-loop (e.g., [0, 0])	The algorithm should detect this cycle and return an empty list, indicating no valid schedule.
prerequisites contains duplicate entries (e.g., [1, 0], [1, 0])	The graph construction logic should handle duplicates by treating them as a single dependency edge.
A cycle exists in the prerequisites, making it impossible to finish all courses	The topological sort algorithm must detect cycles and return an empty list.
numCourses is 1 and prerequisites is empty	Return a list containing only course 0, as only one course exists and has no dependencies.
Large number of courses and prerequisites stressing memory or causing stack overflow with recursion	The solution should use an iterative topological sort approach (e.g., Kahn's algorithm) to avoid stack overflow, and the data structures used should scale efficiently in memory (e.g., adjacency lists).
Multiple valid course orderings exist	The algorithm should return one of the valid orderings, as the problem statement does not require a specific ordering.