What Is In-Degree and Out-Degree? The Graph Concept Interviews Test

You have five tasks. Task 2 needs task 1. Task 3 needs tasks 1 and 2. Task 4 needs task 3. You are the build system. You are panicking.

The tasks you can start right now are the ones nobody is waiting on. That property has a name: in-degree. Specifically, in-degree zero.

In-degree and out-degree are the two simplest properties of a directed graph, and they show up in a surprising number of interview problems disguised as scheduling puzzles and dependency chains. If you have ever solved a course schedule problem, you used in-degree whether you knew it or not.

The Baseline: Undirected Degree

Before directed graphs, a quick calibration. The easy version, with no drama.

In an undirected graph, every node has a single degree: the number of edges connected to it. Direction does not exist, so there is nothing to split.

A -- B -- C
     |
     D

Node B has degree 3. Nodes A, C, and D each have degree 1.

The handshaking lemma holds here: the sum of all degrees always equals 2|E|. Every edge gets counted twice, once for each endpoint. Useful for sanity-checking an edge list when your numbers feel off.

In-Degree and Out-Degree: When Direction Splits the Count

Add direction and each node gets two separate counts:

In-degree: the number of edges pointing into the node
Out-degree: the number of edges pointing out of the node

A → B → D
    ↑
    C

Node	In-degree	Out-degree
A	0	1
B	2	1
C	0	1
D	1	0

The sum of all in-degrees equals the sum of all out-degrees, and both equal the number of edges |E|. Every directed edge contributes exactly one unit to each total: one out-degree at its source, one in-degree at its destination.

Two special node types worth naming:

A source has in-degree 0. Nothing points into it. It depends on nothing. It is free.
A sink has out-degree 0. It points nowhere. Nothing depends on it.

In the example above, A and C are sources. D is a sink. B is the node everyone is waiting on.

Computing Both Takes One Pass

If your graph is an adjacency list, a single scan over the edge list gives you everything:

from collections import defaultdict

def compute_degrees(n: int, edges: list[tuple[int, int]]):
    in_degree = [0] * n
    out_degree = [0] * n

    for src, dst in edges:
        out_degree[src] += 1
        in_degree[dst] += 1

    return in_degree, out_degree

function computeDegrees(n: number, edges: [number, number][]): [number[], number[]] {
    const inDegree = new Array(n).fill(0);
    const outDegree = new Array(n).fill(0);

    for (const [src, dst] of edges) {
        outDegree[src]++;
        inDegree[dst]++;
    }

    return [inDegree, outDegree];
}

Time: O(V + E). You initialize V counters and scan all E edges once. Space: O(V) for the two degree arrays.

If your graph is an adjacency matrix, in-degree of vertex v is the sum of column v, and out-degree is the sum of row v. That is O(V) per node and O(V²) total. Adjacency lists are almost always the right representation. This is not a close call.

Why It Matters in Coding Interviews

Kahn's Algorithm: Topological Sort via In-Degree

The most common interview use of in-degree is Kahn's algorithm, the BFS-based approach to topological sort.

The logic is almost insultingly simple: find every node with in-degree 0 (nobody waiting on it), process them, then subtract their contribution from whoever was waiting on them. When a downstream node's count hits zero, it joins the queue. Repeat until empty.

Kahn's algorithm step by step: sources enter the queue, get processed, and unlock their neighbors

from collections import deque, defaultdict

def topological_sort(n: int, edges: list[tuple[int, int]]) -> list[int]:
    adj = defaultdict(list)
    in_degree = [0] * n

    for src, dst in edges:
        adj[src].append(dst)
        in_degree[dst] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order  # len(order) < n means a cycle exists

function topologicalSort(n: number, edges: [number, number][]): number[] {
    const adj: number[][] = Array.from({ length: n }, () => []);
    const inDegree = new Array(n).fill(0);

    for (const [src, dst] of edges) {
        adj[src].push(dst);
        inDegree[dst]++;
    }

    const queue: number[] = [];
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }

    const order: number[] = [];
    let head = 0;

    while (head < queue.length) {
        const node = queue[head++];
        order.push(node);
        for (const neighbor of adj[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) queue.push(neighbor);
        }
    }

    return order;
}

Time: O(V + E). Every node and every edge is processed exactly once. Space: O(V + E) for the adjacency list and in-degree array.

Cycle Detection for Free

Cycle detection is a side effect of Kahn's algorithm, not a separate pass. If the returned order is shorter than n, some nodes were never enqueued because their in-degree never reached zero. They were stuck in a cycle, each waiting on the next, which was waiting on the next, which was waiting on the first. Nobody moved.

LeetCode 207 (Course Schedule) asks whether you can finish all n courses given a list of prerequisites. The direct translation: does this DAG contain a cycle?

from collections import deque, defaultdict

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    adj = defaultdict(list)
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1

    queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return processed == num_courses

LeetCode 210 (Course Schedule II) is identical except you return the order rather than a boolean. Same algorithm. Slightly different punchline.

The Minimum Starting Set Is Just In-Degree 0

LeetCode 1557 asks: what is the minimum set of nodes from which every other node in a DAG is reachable?

The answer is all nodes with in-degree 0. These are the only nodes that no other node can lead you to. If any source is absent from your starting set, it is unreachable by definition. The code is almost annoyingly short:

def find_smallest_set_of_vertices(n: int, edges: list[list[int]]) -> list[int]:
    has_incoming = set()
    for _, dst in edges:
        has_incoming.add(dst)
    return [i for i in range(n) if i not in has_incoming]

No adjacency list needed. You only care which nodes appear as destinations. Scan once, return the rest.

How to Recognize This Pattern in an Interview

When a problem involves ordering, dependencies, or prerequisites in a directed graph, reach for in-degree first. More specifically:

"Can you complete all X?" → cycle detection via Kahn's
"Find a valid ordering of X" → topological sort via Kahn's
"What is the minimum starting set?" → find all in-degree 0 nodes
"Which nodes have no prerequisites?" → same thing

If you see an edge list where one thing must happen before another, that is a near-certain signal that in-degree is relevant.

Where Candidates Go Wrong

Forgetting to seed the queue with all in-degree 0 nodes. You found one source, threw it in the queue, and moved on. But the graph has three independent starting points. Two entire chains never process. The output looks plausible. It is wrong. The queue seed needs to be every node with in-degree 0, not just the first one.

Getting the edge direction backwards. You built the graph, ran the sort, got a valid-looking ordering, submitted, wrong answer. You stared at the code for ten minutes before noticing the problem says [a, b] means "a requires b" but you built the edge as a → b instead of b → a. The topological sort ran correctly on the wrong graph. The output was silently wrong the whole time. This happens to everyone and it is infuriating every single time.

Using an adjacency matrix for degree computation. Summing a column for in-degree costs O(V) per node. For 10,000 nodes, that is 10^8 operations just to build your degree array. Use an edge list or adjacency list unless the problem forces otherwise.

Key Takeaways

In-degree counts edges coming in; out-degree counts edges going out. Sources have in-degree 0. Sinks have out-degree 0.
Sum of all in-degrees = sum of all out-degrees = |E|.
Computing degrees from an edge list is O(V + E).
Kahn's algorithm is built entirely on in-degree: seed with sources, peel them off, repeat until empty.
Cycle detection is free with Kahn's. If you process fewer than V nodes, the remainder are stuck in a cycle waiting on each other.
The pattern signal: prerequisites, dependencies, ordering constraints in a directed graph means in-degree.

If you want to practice explaining topological sort and in-degree out loud, not just coding them but walking an interviewer through your reasoning in real time, SpaceComplexity runs voice-based mock interviews with rubric-based feedback on exactly that kind of graph reasoning.