medium

Build Order

Find a valid compile order for a list of projects given their pairwise dependencies.

1. Define the problem

Build Order

You are given a list of projects and a list of dependency pairs dependenciesi = [first, second], meaning first must be built before second. Return a valid build order containing every project, or an empty array if no valid order exists because the dependencies form a cycle. Treat each project as a node and each dependency as a directed edge, then peel off projects whose dependencies are already built , one round at a time.

Constraints

  • 1 ≤ projects.length ≤ 2000
  • 0 ≤ dependencies.length ≤ 5000
  • Every value in dependencies is a project from the projects list

Example

Inputprojects = ["a","b","c","d","e","f"], dependencies = [["a","d"],["f","b"],["b","d"],["f","a"],["d","c"]]
Output["e","f","b","a","d","c"] (one valid order — others exist too)

Explanation e and f have no dependencies so they can build first; d needs both a and b, and c needs d.

2. Know the words first

In plain terms

Valid build order
A sequence of every project where each one appears only after everything it depends on.
3. Visualize the solution

Peel projects whose dependencies are already built

Peel projects whose dependencies are already built
Statusinit

In-degree: a=1, b=1, c=1, d=2, e=0, f=0. Queue = [e, f].

What happens in this step

in-degree[a] = 1, in-degree[b] = 1, in-degree[c] = 1, in-degree[d] = 2
in-degree[e] = 0, in-degree[f] = 0

queue = [e, f]

e and f have no unbuilt dependencies, so they start the queue. d is the most constrained project, waiting on both a and b.
Step 1 of 4

Steps to visualize

  1. Build a graph where an edge points from a dependency to the project that needs it, and count in-degrees.
  2. Queue every project with no unbuilt dependencies.
  3. Pop a project, append it to the build order, and decrement the in-degree of everything it unblocks.
  4. Repeat until the queue empties — if every project made it into the order, return it, otherwise a cycle blocked the rest.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Peel projects whose dependencies are already built
Statusinit

In-degree: a=1, b=1, c=1, d=2, e=0, f=0. Queue = [e, f].

What happens in this step

in-degree[a] = 1, in-degree[b] = 1, in-degree[c] = 1, in-degree[d] = 2
in-degree[e] = 0, in-degree[f] = 0

queue = [e, f]

e and f have no unbuilt dependencies, so they start the queue. d is the most constrained project, waiting on both a and b.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function findBuildOrder(projects, dependencies) {
  const inDegree = new Map(projects.map((p) => [p, 0]));
  const graph = new Map(projects.map((p) => [p, []]));

  for (const [first, second] of dependencies) {
    graph.get(first).push(second);
    inDegree.set(second, inDegree.get(second) + 1);
  }

  const queue = projects.filter((p) => inDegree.get(p) === 0);
  const order = [];

  while (queue.length > 0) {
    const project = queue.shift();
    order.push(project);
    for (const next of graph.get(project)) {
      inDegree.set(next, inDegree.get(next) - 1);
      if (inDegree.get(next) === 0) {
        queue.push(next);
      }
    }
  }

  return order.length === projects.length ? order : [];
}
Time
O(projects.length + dependencies.length)
Space
O(projects.length + dependencies.length)
6. Test cases

Test cases

InputExpectedCovers
projects = ["a","b","c","d","e","f"], dependencies = [["a","d"],["f","b"],["b","d"],["f","a"],["d","c"]]contains a, b, c, d, e, fbranching dependencies where multiple orders are valid — checked as a set
projects = ["x","y","z"], dependencies = [["x","y"],["y","z"]]["x", "y", "z"]a strict chain where only one order is possible
projects = ["a","b","c"], dependencies = [["a","b"],["b","c"],["c","a"]][]a three-way cycle makes the build impossible
projects = ["p","q","r"], dependencies = []contains p, q, rno dependencies at all, so any order is valid — checked as a set
projects = ["m","n"], dependencies = [["m","n"],["m","n"]]["m", "n"]the same dependency listed twice does not break the peel
projects = ["solo"], dependencies = []["solo"]smallest valid input, one project with no dependencies
projects = ["core","db","api","ui","auth"], dependencies = [["core","db"],["core","auth"],["db","api"],["auth","api"],["api","ui"]]contains core, db, api, ui, authdb and auth are interchangeable siblings — checked as a set, not one exact sequence
projects = ["a","b","c","d"], dependencies = [["a","b"],["b","a"],["c","d"]][]a cycle between two projects blocks the whole build even though c and d are fine

Keep reading