Swift solution using BFS with full comments


  • 0
    S

    This is a solution based on the best of several approaches discussed. It uses BFS (note the queue) and should make sense to most readers.

    class Solution {
        func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
            // sanity check
            if numCourses == 0 {
                return []
            }
            
            // create count prereqs by course
            var coursePrereqCount = [Int](repeating: 0, count: numCourses)
            for i in 0..<prerequisites.count {
                coursePrereqCount[prerequisites[i][0]] += 1
            }
    
            // our course order result
            var courseOrder: [Int] = []
    
            // find courses with zero prereqs
            // - add to the course taken order
            // - queue taken course to count against prereqs
            var courseTakenQueue: [Int] = []
            for i in 0..<numCourses {
                // if no prereqs, 
                if coursePrereqCount[i] == 0 {
                    courseOrder.append(i)
                    courseTakenQueue.append(i)
                }
            }
            
            // when the queue of satisfied prereqs is empty, we're done
            while !courseTakenQueue.isEmpty{
                let courseTaken = courseTakenQueue.removeFirst()
                // decrements the prereq count for any courses dependent on the course
                for i in 0..<prerequisites.count {
                    if prerequisites[i][1] == courseTaken {
                        // found a dependency
                        let course = prerequisites[i][0]
                        coursePrereqCount[course] -= 1
                        if coursePrereqCount[course] == 0 {
                            // no more prereqs for this course
                            // - add to the course taken order
                            // - queue taken course to count against prereqs
                            courseOrder.append(course)
                            courseTakenQueue.append(course)
                        }
                    }
                }
            }
            
            // if we have an order which includes all numCourses, return it, otherwise empty
            return courseOrder.count == numCourses ? courseOrder : []
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.