SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Determine if it is possible to finish all courses given the number of courses and the prerequisites for each course. Each course is labeled from 0 to numCourses - 1. You are given a list of prerequisite pairs, where prerequisites[i] = [ai, bi] indicates that you must take course bi before course ai.

Intuition

The problem can be reduced to detecting if there is a cycle in a directed graph. If there is a cycle, it's impossible to complete all courses. We use topological sorting (Kahn's algorithm) to detect cycles and determine the order of courses.

Approach

1. Graph Representation:

   • Use an adjacency matrix to represent the graph.
   • Use an array to keep track of the number of prerequisites each course has.

2. Topological Sorting:

   • Initialize a queue to store courses with no prerequisites.
   • Use BFS to process each course, decrementing the prerequisite count of connected courses.
   • Add courses with no remaining prerequisites to the queue.

3. Cycle Detection:

   • If the number of processed courses equals numCourses, all courses can be finished.
   • If not, there is a cycle in the graph, making it impossible to finish all courses.

Complexity

Time Complexity:

• Constructing the graph takes O(P) time, where P is the number of prerequisites.
• Topological sorting takes O(V + E) time, where V is the number of courses and E is the number of prerequisites.
• Total time complexity is O(V + P).

Space Complexity:

• The adjacency matrix takes O(V^2) space.
• The requirements array takes O(V) space.
• The queue takes up to O(V) space.
• Total space complexity is O(V^2).

Code

C++

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        if (numCourses <= 1 || prerequisites.empty()) {
            return true;
        }
        vector<vector<int>> matrix(numCourses, vector<int>(numCourses, 0));
        vector<int> requirements(numCourses, 0);

        for (const auto& each : prerequisites) {
            int course = each[0];
            int pre = each[1];
            if (matrix[pre][course] == 0) {
                requirements[course]++;
            }
            matrix[pre][course] = 1;
        }
        queue<int> stack;
        for (int i = 0; i < numCourses; ++i) {
            if (requirements[i] == 0) {
                stack.push(i);
            }
        }
        int counter = 0;
        while (!stack.empty()) {
            int course = stack.front();
            stack.pop();
            counter++;
            for (int i = 0; i < numCourses; ++i) {
                if (matrix[course][i] != 0) {
                    requirements[i]--;
                    if (requirements[i] == 0) {
                        stack.push(i);
                    }
                }
            }
        }
        return counter == numCourses;
    }
};

Python

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if numCourses <= 1 or not prerequisites:
            return True

        matrix = [[0] * numCourses for _ in range(numCourses)]
        requirements = [0] * numCourses

        for course, pre in prerequisites:
            if matrix[pre][course] == 0:
                requirements[course] += 1
            matrix[pre][course] = 1

        stack = [i for i in range(numCourses) if requirements[i] == 0]
        counter = 0
        while stack:
            course = stack.pop(0)
            counter += 1
            for i in range(numCourses):
                if matrix[course][i] != 0:
                    requirements[i] -= 1
                    if requirements[i] == 0:
                        stack.append(i)

        return counter == numCourses

Java

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 1 || prerequisites == null || prerequisites.length <= 1) {
            return true;
        }
        int[][] matrix = new int[numCourses][numCourses];
        int[] requirements = new int[numCourses];

        for (int[] each : prerequisites) {
            int course = each[0];
            int pre = each[1];
            if (matrix[pre][course] == 0) {
                requirements[course]++;
            }
            matrix[pre][course] = 1;
        }
        java.util.Queue<Integer> stack = new java.util.LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (requirements[i] == 0) {
                stack.add(i);
            }
        }
        int counter = 0;
        while (!stack.isEmpty()) {
            int course = stack.poll();
            counter++;
            for (int i = 0; i < numCourses; i++) {
                if (matrix[course][i] != 0) {
                    requirements[i]--;
                    if (requirements[i] == 0) {
                        stack.add(i);
                    }
                }
            }
        }
        return counter == numCourses;
    }
}

JavaScript

var canFinish = function (numCourses, prerequisites) {
    if (numCourses <= 1 || !prerequisites || prerequisites.length <= 1) {
        return true;
    }
    const matrix = Array.from({ length: numCourses }, () => new Array(numCourses).fill(0));
    const requirements = new Array(numCourses).fill(0);
    prerequisites.forEach(each => {
        const [course, pre] = each;
        if (matrix[pre][course] === 0) {
            requirements[course]++;
        }
        matrix[pre][course] = 1;
    });
    const stack = [];
    requirements.forEach((each, index) => {
        if (each === 0) {
            stack.push(index);
        }
    });
    let counter = 0;
    while (stack.length) {
        const course = stack.shift();
        counter++;
        for (let i = 0; i < numCourses; i++) {
            if (matrix[course][i] !== 0) {
                requirements[i]--;
                if (requirements[i] === 0) {
                    stack.push(i);
                }
            }
        }
    }
    return counter === numCourses;
};