Course Schedule

Medium

eBay

0 views

Topics:

Graphs

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 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 <= a_i, b_i < numCourses
All the pairs prerequisites[i] are unique.

Course Schedule

Medium

eBay

0 views

Topics:

Graphs

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 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 <= a_i, b_i < numCourses
All the pairs prerequisites[i] are unique.

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?
Can I assume that there are no self-loops in the `prerequisites` list (i.e., `[a, a]` does not exist)?
If it is impossible to finish all courses, what should the return value be?
Are there any duplicate prerequisite pairs in the `prerequisites` list? If so, should they be treated as a single prerequisite?
Are the course numbers in the `prerequisites` list guaranteed to be within the range [0, numCourses - 1]?

Brute Force Solution

Approach

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:

Start by considering all the different orderings of the courses.
For each ordering, check if you can actually take the courses in that order, respecting all prerequisite requirements.
This means ensuring that for every course, you've already taken all the courses that it depends on before attempting to take that course.
If you find an ordering where you can take all the courses without violating any prerequisites, then you know it's possible to complete all the courses.
If you go through all possible orderings and none of them work, then it's impossible to complete all the courses.

Code Implementation

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

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n! * m * n) – The brute force solution explores all possible permutations of courses, which results in n! (n factorial) possible orderings where n is the number of courses. For each of these orderings, we iterate through the courses (n) and check if the prerequisites are satisfied. Checking the prerequisites for each course involves iterating through the prerequisite list (m, the average number of prerequisites per course). Therefore, the time complexity is proportional to n! for generating the permutations, multiplied by n * m for validating each permutation. This gives us O(n! * m * n), or simplified, O(n! * n) if we assume m is relatively small or constant compared to n.

Space Complexity

O(N!) – The brute force approach generates all possible orderings of courses. Each ordering requires storing N courses, and in the worst case, there are N! (N factorial) possible orderings to explore simultaneously in memory during the exhaustive search. While checking each ordering, no other significant data structures are created. Therefore, the space complexity is dominated by the storage of these permutations, leading to O(N!) auxiliary space.

Optimal Solution

Approach

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:

Think of the courses as items in a to-do list and the dependencies as connections between them.
First, identify all the courses that don't have any prerequisites. These are courses you can take right away.
Now, start taking those courses. As you 'take' a course, remove it from the list and also remove it from the prerequisites of other courses.
Keep taking courses that have no remaining prerequisites, and removing them as prerequisites for other courses.
If at any point you can't find a course with no prerequisites, but you still have courses left, it means there's a circular dependency, and you can't take all the courses.
If you successfully take all the courses in this manner, it means you can complete the course schedule.

Code Implementation

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

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(V + E) – The algorithm iterates through all courses (V vertices) and their prerequisites (E edges). Finding initial courses with no prerequisites involves examining each prerequisite relationship. Then, the algorithm simulates taking courses, which includes updating the in-degrees of dependent courses. This update process involves traversing the adjacency list representing the course dependencies, which takes O(E) time in total. Therefore, the overall time complexity is driven by the number of courses (V) and the number of dependencies (E), resulting in O(V + E).

Space Complexity

O(N) – The algorithm requires storing courses with no prerequisites in an auxiliary data structure, which in the worst-case scenario, could contain all N courses. Additionally, the algorithm keeps track of dependencies and removes them, potentially requiring auxiliary space proportional to the number of courses. Therefore, the auxiliary space used is primarily determined by the number of courses, resulting in a space complexity of O(N), where N represents the number of courses.

Edge Cases

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.