Medium

Course Schedule II

070

Return one valid course ordering for numCourses and prerequisites, or [] if impossible. Use the lexicographically smallest valid order.

EXAMPLES

Example 1

Input
{
  "numCourses": 4,
  "prerequisites": [
    [
      1,
      0
    ],
    [
      2,
      0
    ],
    [
      3,
      1
    ],
    [
      3,
      2
    ]
  ]
}

Output
[
  0,
  1,
  2,
  3
]

FUNCTION SHAPE

numCourses: intprerequisites: intMatrix→intArray

SOLUTION NOTE

This is exactly the same, but instead of a boolean we want to return the topological ordering.

Reveal reference solution +

pythonREFERENCE

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    adjList = defaultdict(list)
    indegree = [0] * numCourses

    for u,v in prerequisites:
        adjList[v].append(u)
        indegree[u] += 1

    q = deque([i for i in range(numCourses) if indegree[i] == 0])

    top_order = []

    while q:
        u = q.popleft()
        top_order.append(u)

        for nbr in adjList[u]:
            indegree[nbr] -= 1
            if indegree[nbr] == 0:
                q.append(nbr)

    return top_order if len(top_order) == numCourses else []

TimeO(V + E)

SpaceO(V + E)

Open on LeetCode ↗