Course Schedule

Problem

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

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

Solution

Another Topological Sort

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        var m = new boolean[numCourses][numCourses];
        var indegree = new int[numCourses];
        var s = new Stack<Integer>();

        for (var p : prerequisites) {
            m[p[0]][p[1]] = true;
            indegree[p[0]] += 1;
        }

        for (var i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                s.push(i);
            }
        }

        var complete = 0;
        while (!s.isEmpty()) {
            var c = s.pop();
            complete += 1;
            for (var i = 0; i < numCourses; i++) {
                if (m[i][c]) {
                    indegree[i] -= 1;
                    if (indegree[i] == 0) {
                        s.push(i);
                    }
                }
            }
        }

        return complete == numCourses;
    }
}

Recursive DFS

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // using DFS
        var m = new boolean[numCourses][numCourses];
        var gVisited = new boolean[numCourses];
        var lVisited = new boolean[numCourses];

        for (var p : prerequisites) {
            m[p[0]][p[1]] = true;
        }

        for (var i = 0; i < numCourses; i++) {
            if (!dfs(i, numCourses, m, gVisited, lVisited)) {
                return false;
            }
        }

        return true;
    }

    public boolean dfs(int i, int n, boolean[][] m, boolean[] gVisited, boolean[] lVisited) {
        if (lVisited[i]) {
            return false;
        }

        if (gVisited[i]) {
            return true;
        }

        gVisited[i] = true;
        lVisited[i] = true;

        // loop over every course that this vertex has an edge to
        for (var x = 0; x < n; x++) {
            if (m[i][x]) {
                // perform a dfs on x
                if (!dfs(x, n, m, gVisited, lVisited)) {
                    return false;
                }
            }
        }

        lVisited[i] = false;
        return true;
    }
}

Topological Sort

If the input can be topologically sorted (and thus that the input forms a DAG), then we know that the course schedule is possible.

First try!

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        var indegree = new int[numCourses];
        var matrix = new boolean[numCourses][numCourses];
        for (var pair : prerequisites) {
            var course = pair[0];
            var prereq = pair[1];
            indegree[course] += 1;
            matrix[course][prereq] = true;
        }

        var next = new Stack<Integer>();

        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                next.push(i);
                // mark this node as complete
                indegree[i] = -1;
            }
        }

        while (!next.isEmpty()) {
            var c = next.pop();
            for (int i = 0; i < numCourses; i++) {
                if (matrix[i][c] == true) {
                    indegree[i] -= 1;
                    if (indegree[i] == 0) {
                        indegree[i] = -1;
                        next.push(i);
                    }
                }
            }
        }

        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] != -1) {
                return false;
            }
        }

        return true;
    }
}

Recent posts from blogs that I like

An Introduction to Google’s Approach to AI Agent Security

via Simon Willison

Notes on Cramer's rule

Cramer's rule is a clever solution to the classical system of linear equations Ax=b: \[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}b_1 \\ b_2 \\ b_3\end{bmatrix}\] Usi...

via Eli Bendersky

Brandjes: Paintings as witnesses to fires 1640-1813

Dramatic paintings of towns and cities on fire, usually at night, were popular during the Dutch Golden Age, and known as brandjes. Examples to well into the 19th century.

via The Eclectic Light Company