Course Schedule II

Medium

Netflix

4 views

Topics:

GraphsDynamic Programming

You are given numCourses courses labeled from 0 to numCourses - 1. You are also given a list of prerequisites, where prerequisites[i] = [a_i, b_i] means you must take course b_i before course a_i. For example, [0, 1] means you must take course 1 before course 0.

Your task is to return an ordering of courses that allows you to complete all courses. If multiple orderings are possible, return any one of them. If it's impossible to complete all courses due to a circular dependency, return an empty array.

Example 1:

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

Output: [0,1] (To take course 1, you must take course 0 first)

Example 2:

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

Output: [0,2,1,3] (Course 3 depends on 1 and 2, which depend on 0)

Example 3:

numCourses = 1, prerequisites = []

Output: [0] (A single course with no dependencies)

Develop an efficient algorithm to solve this course scheduling problem. Consider edge cases such as circular dependencies and courses with no dependencies.

Course Schedule II

Medium

Netflix

4 views

Topics:

GraphsDynamic Programming

You are given numCourses courses labeled from 0 to numCourses - 1. You are also given a list of prerequisites, where prerequisites[i] = [a_i, b_i] means you must take course b_i before course a_i. For example, [0, 1] means you must take course 1 before course 0.

Your task is to return an ordering of courses that allows you to complete all courses. If multiple orderings are possible, return any one of them. If it's impossible to complete all courses due to a circular dependency, return an empty array.

Example 1:

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

Output: [0,1] (To take course 1, you must take course 0 first)

Example 2:

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

Output: [0,2,1,3] (Course 3 depends on 1 and 2, which depend on 0)

Example 3:

numCourses = 1, prerequisites = []

Output: [0] (A single course with no dependencies)

Develop an efficient algorithm to solve this course scheduling problem. Consider edge cases such as circular dependencies and courses with no dependencies.

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.