NUHMAN.com

Problem Statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. Some courses have prerequisites, and you must take those prerequisites before taking the respective course.

Given the integer numCourses and a list of prerequisite pairs prerequisites (where each pair [a, b] indicates that you must take course b before course a), return true if you can finish all courses, otherwise return false.

Function Signature:

go

func canFinish(numCourses int, prerequisites [][]int) bool

Example 1:

go

numCourses := 2
prerequisites := [][]int{{1, 0}}

fmt.Println(canFinish(numCourses, prerequisites)) 
// Output: true

Explanation: There are 2 courses, and you can finish all of them by taking course 0 first, then course 1.

Example 2:

go

numCourses := 2
prerequisites := [][]int{{1, 0}, {0, 1}}

fmt.Println(canFinish(numCourses, prerequisites)) 
// Output: false

Explanation: This results in a cycle where course 1 requires course 0, and course 0 requires course 1, which makes it impossible to finish the courses.

Constraints:

• 1 <= numCourses <= 10^5
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= prerequisites[i][0], prerequisites[i][1] < numCourses

Approach

This problem can be visualized as a directed graph where each course is a node, and the prerequisite relationship represents a directed edge. The goal is to detect whether the graph contains a cycle because a cycle indicates that there is a circular dependency, making it impossible to finish all the courses.

We can solve this problem using topological sorting. If we can find a valid topological ordering of the courses, then it's possible to finish all the courses. If we cannot find such an ordering (i.e., the graph contains a cycle), then it's not possible to finish the courses.

Approach Using DFS:

1. Graph Representation:

• Build a graph using adjacency lists where each course has a list of courses that depend on it (prerequisites).

1. Cycle Detection with DFS:

• We can use a DFS traversal to detect cycles in the graph. If we revisit a course that is already being processed (marked as visiting), then there's a cycle.
• Courses can have three states:
• Unvisited: Not processed yet.
• Visiting: Currently being processed (in the DFS stack).
• Visited: Fully processed and no cycle detected for that course.

1. DFS Traversal:

• Start DFS for each course. If we encounter a course that is currently in the "visiting" state, it means a cycle is present, and we should return false.
• After the DFS for a course completes, mark it as "visited."

Time Complexity:

• O(V + E), where V is the number of courses (vertices), and E is the number of prerequisite relationships (edges). Each course and each edge is processed once during the DFS traversal.

Space Complexity:

• O(V + E), for the adjacency list and the state tracking of each course.

Go Implementation

go

package main

import "fmt"

// Function to check if it's possible to finish all courses
func canFinish(numCourses int, prerequisites [][]int) bool {
    // Create the adjacency list for the graph
    adjList := make([][]int, numCourses)
    for _, prereq := range prerequisites {
        adjList[prereq[1]] = append(adjList[prereq[1]], prereq[0])
    }

    // Create a state array to track each course's state
    // 0: unvisited, 1: visiting, 2: visited
    state := make([]int, numCourses)

    // Helper function for DFS
    var dfs func(course int) bool
    dfs = func(course int) bool {
        if state[course] == 1 { // Course is being visited, cycle detected
            return false
        }
        if state[course] == 2 { // Course already processed, no cycle
            return true
        }

        state[course] = 1 // Mark course as visiting
        for _, nextCourse := range adjList[course] {
            if !dfs(nextCourse) {
                return false // Cycle detected in the DFS
            }
        }

        state[course] = 2 // Mark course as visited
        return true
    }

    // Check each course
    for i := 0; i < numCourses; i++ {
        if state[i] == 0 { // If the course is unvisited
            if !dfs(i) {
                return false // If DFS detects a cycle
            }
        }
    }

    return true // All courses can be finished
}

// Main function to test the solution
func main() {
    // Test case 1
    numCourses1 := 2
    prerequisites1 := [][]int{{1, 0}}
    fmt.Println(canFinish(numCourses1, prerequisites1)) // Output: true

    // Test case 2
    numCourses2 := 2
    prerequisites2 := [][]int{{1, 0}, {0, 1}}
    fmt.Println(canFinish(numCourses2, prerequisites2)) // Output: false
}

Explanation of the Code:

1. Graph Representation (Adjacency List):

• We represent the graph as an adjacency list (adjList) where each node (i) has a list of nodes (j) that depend on it (i.e., j must be completed before i).

2. State Array:

• We use an array state to track the state of each course during the DFS:
• 0: The course has not been visited yet.
• 1: The course is currently being processed (it's in the DFS stack).
• 2: The course has been fully processed (no cycle detected).

3. DFS Traversal:

• We perform DFS for each course, starting from unvisited courses. If at any point, we revisit a course that is in the "visiting" state (cycle detected), we return false.
• After successfully processing all dependencies for a course, we mark it as "visited."

4. Main Function:

• The main function tests the solution with two test cases:
• The first test case checks if courses can be finished when there is a valid prerequisite chain.
• The second test case checks for a cycle in the graph and returns false.

Example Walkthrough

Example 1:

Input:

go

numCourses := 2
prerequisites := [][]int{{1, 0}}

The graph is:

rust

0 -> 1

• Course 1 depends on course 0. There's no cycle, so all courses can be completed.
• Output: true

Example 2:

Input:

go

numCourses := 2
prerequisites := [][]int{{1, 0}, {0, 1}}

The graph is:

rust

0 -> 1
1 -> 0

• There's a cycle: course 1 depends on course 0, and course 0 depends on course 1. It's impossible to complete all courses.
• Output: false

Conclusion

LeetCode 207: Course Schedule can be efficiently solved using DFS and cycle detection. The graph-based approach ensures that we can detect whether the prerequisites can be completed or not, based on the presence of cycles in the course dependencies.