FrontendPro

147Implement a dependency resolver using topological sorting

hardAbout 60 minutesCodinggraphstopological-sortdfskahn

Problem

Package managers, build tools and module bundlers all need to know what to install or build first. Implement:

  1. findOrder(numCourses, prerequisites) (LeetCode 210): prerequisites are pairs [a, b] meaning "take b before a". Return any order that takes every course, or [] if it is impossible (a cycle).
  2. resolveInstallOrder(packages): packages maps a name to its dependency names, for example { app: ["react", "router"], router: ["react"], react: [] }. Return the install order (dependencies before dependents). Make it deterministic: when several packages are ready, take them in alphabetical order. Throw an Error:
    • Unknown dependency "x" required by "y" when a dependency is not in packages;
    • Circular dependency: a -> b -> a (the actual cycle path) when there is a cycle.

Try it yourself

Write your solution, run it, then submit to check it against the tests.

solution.jsJavaScript

Press Run or ⌘ Enter to execute your code.

Video walkthrough

Stuck? Watch someone solve it, then try again on your own.

Course Schedule II - Topological Sort - Leetcode 210NeetCode on YouTubeOpen on YouTube

Step-by-step

Draw an edge from each prerequisite to the course that needs it. A valid order is a topological order: every edge points forward. It exists exactly when the graph has no cycle.

Unlock the full solution

What's inside

  • Step-by-step
  • Approach
  • Solution
  • Complexity
  • Edge cases
  • Follow-up questions
  • Tests

Includes 2 code listings, 5 edge cases, 4 follow-up questions.

One-time payment by UPI, card or net banking. Launch price.

All 150 answersOne payment, yours forever