NUHMAN.com

Problem Statement

There are numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] means: to take course a, you must first take course b.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example

go

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3] or [0,1,2,3]

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= a, b < numCourses
• All the pairs are unique.

Approach

We'll use Topological Sorting using Kahn’s Algorithm (BFS-based):

1. Build an adjacency list and an in-degree map.
2. Add courses with in-degree 0 to the queue.
3. Repeatedly pop from the queue and reduce the in-degree of neighbors.
4. If we can process all courses, return the topological order. Otherwise, return an empty array (cycle exists).

Go Implementation

go

package main

import "fmt"

func findOrder(numCourses int, prerequisites [][]int) []int {
    graph := make(map[int][]int)
    inDegree := make([]int, numCourses)

    // Build graph and in-degree array
    for _, pre := range prerequisites {
        a, b := pre[0], pre[1]
        graph[b] = append(graph[b], a)
        inDegree[a]++
    }

    // Queue for courses with no prerequisites
    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    order := []int{}
    for len(queue) > 0 {
        course := queue[0]
        queue = queue[1:]
        order = append(order, course)

        for _, neighbor := range graph[course] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    if len(order) == numCourses {
        return order
    }
    return []int{}
}

// Example usage
func main() {
    numCourses := 4
    prerequisites := [][]int{{1, 0}, {2, 0}, {3, 1}, {3, 2}}
    result := findOrder(numCourses, prerequisites)
    fmt.Println("Course order:", result)
}

Explanation

• Graph Construction: Represents course dependencies.
• In-Degree: Tracks how many prerequisites each course has.
• Queue: Starts with courses that have no prerequisites.
• Topological Order: Append as courses are completed and prerequisites are cleared.

Time and Space Complexity

• Time Complexity: O(V + E) = O(numCourses + prerequisites.length)
• Space Complexity: O(V + E) for graph and in-degree structures.

Conclusion

This problem is a classic application of Topological Sorting to determine task/course scheduling with dependency constraints.

Let me know if you want the DFS version with cycle detection as well!