LeetCode: Course Schedule – Prepare For Coder Interview

Course Schedule

Similar Problems:

There are a total of n courses you have to take, labeled from 0 to n – 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

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.

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

Hints:

This problem is equivalent to finding if a cycle exists in a directed graph.
Topological Sort via DFS
Topological sort could also be done via BFS.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: Kahn’s algorithm (BFS) without deleting edges

// https://code.dennyzhang.com/course-schedule
// Basic Ideas: topological sort + Kahn's algorithm
//
//  BFS
//    queue: unexamined nodes with no incoming edges
//    Decrease count of incoming edges for the target nodes
//    Get the next nodes to be examined
//
//  When to stop?
//    When BFS stops, there should be no unexamined edges
//    Or all nodes get examined
//
//  Follow-up: what if there are duplicate edges?
//
// Complexity: Time O(n+e), Space O(n+e)
func canFinish(numCourses int, prerequisites [][]int) bool {
    indegrees := make([]int, numCourses)
    edges := map[int]map[int]bool{}
    for _, p := range prerequisites {
        n1, n2 := p[0], p[1]
        if _, ok := edges[n1]; !ok {
            edges[n1] = map[int]bool{}
        }
        edges[n1][n2] = true
        indegrees[n2]++
    }
    count := 0
    queue := []int{}
    for i, v := range indegrees {
        if v == 0 {
            queue = append(queue, i)
            count++
        }
    }
    for len(queue) > 0 {
        l := []int{}
        for _, n1 := range queue {
            for n2, _ := range edges[n1] {
                indegrees[n2]--
                if indegrees[n2] == 0 {
                    l = append(l, n2)
                    count++
                }
            }
        }
        queue = l
    }
    return count == numCourses
}

Solution: Kahn’s algorithm (BFS)

// https://code.dennyzhang.com/course-schedule
// Basic Ideas: topological sort + Kahn's algorithm
//
//  BFS
//    queue: unexamined nodes with no incoming edges
//    Decrease count of incoming edges for the target nodes
//    Get the next nodes to be examined
//
//  When to stop?
//    When BFS stops, there should be no unexamined edges
//
//  Follow-up: what if there are duplicate edges?
//
// Complexity: Time O(n+e), Space O(n+e)
func canFinish(numCourses int, prerequisites [][]int) bool {
    indegrees := make([]int, numCourses)
    edges := map[int]map[int]bool{}
    for _, p := range prerequisites {
        n1, n2 := p[0], p[1]
        if _, ok := edges[n1]; !ok {
            edges[n1] = map[int]bool{}
        }
        edges[n1][n2] = true
        indegrees[n2]++
    }
    queue := []int{}
    for i, v := range indegrees {
        if v == 0 {
            queue = append(queue, i)
        }
    }
    for len(queue) > 0 {
        l := []int{}
        for _, n1 := range queue {
            for n2, _ := range edges[n1] {
                indegrees[n2]--
                if indegrees[n2] == 0 {
                    l = append(l, n2)
                }
            }
            // remove edges
            delete(edges, n1)
        }
        queue = l
    }
    return len(edges) == 0
}

Solution: DFS with recursive

// https://code.dennyzhang.com/course-schedule
// Basic Ideas: topological sort + dfs
//
//    dfs from unexamined nodes with no incoming edges
//    Decrease count of incoming edges for the target nodes
//    Get the next nodes to be examined
//
//  When to stop?
//    When dfs stops, there should be no unexamined edges
//
//  Follow-up: what if there are duplicate edges?
//
// Complexity: Time O(n+e), Space O(n+e)
func dfs(node int, count *int, indegrees []int, edges map[int]map[int]bool) {
    if indegrees[node] != 0 {
        return
    }
    *count++
    for node2, _ := range edges[node] {
        indegrees[node2]--
        dfs(node2, count, indegrees, edges)
    }
    // already visited to avoid duplicate caculation, which could mislead the counter
    indegrees[node] = -1 
}

func canFinish(numCourses int, prerequisites [][]int) bool {
    indegrees := make([]int, numCourses)
    edges := map[int]map[int]bool{}
    for _, p := range prerequisites {
        n1, n2 := p[0], p[1]
        if _, ok := edges[n1]; !ok {
            edges[n1] = map[int]bool{}
        }
        edges[n1][n2] = true
        indegrees[n2]++
    }
    count := 0
    for node, _ := range indegrees {
        dfs(node, &count, indegrees, edges)
    }
    return count == numCourses
}

Solution: DFS without recursive

// https://code.dennyzhang.com/course-schedule
// https://code.dennyzhang.com/course-schedule
// Basic Ideas: topological sort + dfs
//
//    dfs from unexamined nodes with no incoming edges
//    Decrease count of incoming edges for the target nodes
//    Get the next nodes to be examined
//
//  When to stop?
//    When dfs stops, there should be no unexamined edges
//
//  Follow-up: what if there are duplicate edges?
//
// Complexity: Time O(n+e), Space O(n+e)
func canFinish(numCourses int, prerequisites [][]int) bool {
    indegrees := make([]int, numCourses)
    edges := map[int]map[int]bool{}
    for _, p := range prerequisites {
        n1, n2 := p[0], p[1]
        if _, ok := edges[n1]; !ok {
            edges[n1] = map[int]bool{}
        }
        edges[n1][n2] = true
        indegrees[n2]++
    }
    count := 0
    l := []int{}
    for i, v := range indegrees {
        if v == 0 {
            l = append(l, i)
            count++
        }
    }
    for len(l) > 0 {
        n1 := l[0]
        l = l[1:len(l)]
        for n2, _ := range edges[n1] {
            indegrees[n2]--
            if indegrees[n2] == 0 {
                count++
                l = append(l, n2)
            }
        }
    }
    return count == numCourses
}

Solution: Brutle force BFS

// https://code.dennyzhang.com/course-schedule
// Basic Ideas: topological sort
//
//  BFS
//  Start with nodes without dependencies
//  Once used one path, decrease counter for the target node by 1 
//
//  When to stop?
//   When all nodes get visited, there should be no unused edges
//
// Complexity: Time O(n^2), Space O(n)
func canFinish(numCourses int, prerequisites [][]int) bool {
    // when -1: visited. Otherwise how many edges point to this node
    nodes := make([]int, numCourses)
    edges := map[int][]int{}
    for _, p := range prerequisites {
        n1, n2 := p[0], p[1]
        edges[n1] = append(edges[n1], n2)
        nodes[n2]++
    }
    queue := []int{}
    for i, v := range nodes {
        if v == 0 {
            // mark as visited
            nodes[i] = -1
            queue = append(queue, i)
        }
    }
    for len(queue) > 0 {
        for _, n1 := range queue {
            for _, n2 := range edges[n1] {
                // detect deadlock
                if nodes[n2] == -1 {
                    return false
                }
                // use the edge
                nodes[n2]--
            }
        }
        // find the next nodes
        l := []int{}
        for i, v := range nodes {
            if v == 0 {
                nodes[i] = -1
                l = append(l, i)
            }
        }
        queue = l
    }

    // all nodes used
    for _, v := range nodes {
        if v != -1 {
            return false
        }
    }
    return true
}

Post Views: 5