Skip to content
Hello Python

Maintain an Indegree Frontier

Practice ExerciseInterviewEasyKahn's Algorithm

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement kahn_frontier_layers(node_count, edges). Each [before, after] edge points from before to after. Return sorted zero-indegree layers in processing order. Return an empty list if not all nodes can be processed.

Starter code

def kahn_frontier_layers(node_count, edges):
    pass
Test cases

layered-dag

{
  "args": [
    5,
    [
      [
        0,
        2
      ],
      [
        1,
        2
      ],
      [
        2,
        3
      ],
      [
        2,
        4
      ]
    ]
  ]
}

Expected: [[0,1],[2],[3,4]]

independent-nodes

{
  "args": [
    3,
    []
  ]
}

Expected: [[0,1,2]]

Wizard outline
  1. Step 1: Emit the zero-indegree frontier

    Build adjacency and indegree state, then return all initially available nodes as one sorted layer. Kahn traversal begins with exactly the nodes whose prerequisites count is zero.

  2. Step 2: Release successive layers

    Process one sorted frontier at a time, decrement outgoing indegrees, and collect newly released nodes. Every decrement represents one satisfied prerequisite; zero is the exact condition for the next layer.

  3. Step 3: Reject an incomplete cycle order

    Count processed nodes and return an empty result when a cycle prevents all nodes from reaching indegree zero. The traversal layers are valid only if they cover every node in the graph.

Footguns and prerequisites
  • Reversing each edge increments the prerequisite indegree instead of the dependent node’s indegree.
  • Returning processed layers without comparing the processed count silently accepts directed cycles.
  • trees and graphs
Reviewed references
Prepared Interview Problems
  • Course Schedule(opens in a new tab)

    Maintain an Indegree Frontier isolates a node enters a frontier exactly when all of its predecessors have been removed, and each edge decrements indegree once. That focused state discipline is required when implementing course schedule as a complete Interview Problem.

Recommended approach and implementation

Dependency graphs expose currently available work as the nodes with zero remaining incoming edges. A node enters a frontier exactly when all of its predecessors have been removed, and each edge decrements indegree once.

Why it works: Zero-indegree nodes form the available layer, and removing them updates each outgoing dependency exactly once. If every node is emitted the layers respect all edges; otherwise the remaining positive indegrees certify a directed cycle.

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1
    frontier = [node for node, degree in enumerate(indegree) if degree == 0]
    layers = []
    processed = 0
    while frontier:
        frontier.sort()
        layers.append(frontier)
        next_frontier = []
        for node in frontier:
            processed += 1
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    next_frontier.append(neighbor)
        frontier = next_frontier
    return layers if processed == node_count else []