Swift solution - Topological Sort


  • 0
    class Solution {
        func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
            if numCourses == 0 {
                return []
            }
            
            var result = [Int](repeatElement(0, count: numCourses))
            var inDegree = [Int](repeatElement(0, count: numCourses))
            var index = 0
            var queue = [Int]()
            
            for i in 0..<prerequisites.count {
                inDegree[prerequisites[i][0]] += 1
            }
            for i in 0..<numCourses {
                if inDegree[i] == 0 {
                    result[index] = i
                    index += 1
                    queue.append(i)
                }
            }
            while !queue.isEmpty {
                let prerequisite = queue.removeFirst()
                for i in 0..<prerequisites.count {
                    if prerequisites[i][1] == prerequisite {
                        inDegree[prerequisites[i][0]] -= 1
                        if inDegree[prerequisites[i][0]] == 0 {
                            result[index] = prerequisites[i][0]
                            index += 1
                            queue.append(prerequisites[i][0])
                        }
                    }
                }
            }
            
            return (index == numCourses) ? result : []
        }
    }
    

Log in to reply
 

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