Skip to main content

Degree

In-degree and out-degree - how many edges point into and out of a node - are enough to answer a surprising range of graph questions without ever building an adjacency list or traversing an edge. Counting those two arrays over the raw edge list is the whole trick.

The definitions, the source/sink signal table, the handshake lemma and the self-check it gives you are on Graph Anatomy. This page is the practice set.

Sink & Source Identification​

Find the one node whose degree hits an exact target - 0 for a plain source/sink, or n - 1 for a node everyone else points at.

997. Find the Town Judge​

Easy·
2 Approachesclick to switch
Explanation

The town judge is defined by two conditions: everyone else trusts the judge (in-degree n - 1) and the judge trusts nobody (out-degree 0). Count both degrees for every person from the trust pairs, then scan people 1..n for the one node satisfying both. Iterating over range(1, n + 1) - rather than only the nodes that appear in trust - handles the single-person case (n = 1, empty trust) for free: node 1 has in-degree 0 == n - 1 and out-degree 0.

The magic number is n - 1, a fixed value from the input - not something derived from the trust data (like the number of trust pairs), which is a common trap.

Analysis
Time
O(n + E)
  • One pass over the E trust pairs to build the degree arrays - O(E).
  • One pass over the n people to find the judge - O(n).
Space
O(n)
  • in_degree and out_degree are each size n + 1 - O(n).
FIG. 997 FIND THE TOWN JUDGE DEGREE● INTERACTIVE
visualization loads as you reach it
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
in_degree = [0 for i in range(n + 1)]
out_degree = [0 for i in range(n + 1)]
for a, b in trust:
out_degree[a] += 1
in_degree[b] += 1
for node in range(1, n + 1):
if in_degree[node] == n - 1 and out_degree[node] == 0:
return node
return -1

1436. Destination City​

Easy·
Explanation

The destination city is the one path never leaves from - it has out-degree 0. Walk every [a, b] pair, bumping a's out-degree and making sure b is registered with an out-degree of at least 0 (via .get(b, 0)). The one city whose out-degree is 0 is the destination.

Analysis
Time
O(2n)
  • n = number of paths. The for a, b in paths loop builds out_degree in one pass - O(n).
  • The for i, j in out_degree.items() loop scans the map for the city with out-degree 0 - another O(n) pass. Two separate passes give 2n.
Space
O(n)
  • out_degree holds at most n + 1 cities, one per distinct city seen across all n paths.
FIG. 1436 DESTINATION CITY OUT DEGREE● INTERACTIVE
visualization loads as you reach it
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
out_degree = {}
for a, b in paths:
out_degree[a] = out_degree.get(a, 0) + 1
out_degree[b] = out_degree.get(b, 0)
for i, j in out_degree.items():
if j == 0:
return i
return ans

1557. Minimum Number of Vertices to Reach All Nodes​

Medium·
Explanation

The graph is a DAG, so any node with in-degree > 0 is reachable from whichever node has an edge into it - and transitively from that node's ancestors. Following those edges back far enough always bottoms out at a node with in-degree 0, since a DAG has no cycle to loop back into. That makes every in-degree-0 node unreachable from anywhere else, so all of them must be included, and reachable from any starting set, so none of the other nodes need to be.

Count in-degree by scanning edges once, then collect every index whose in-degree is still 0.

Analysis
Time
O(n + E)
  • One pass over the E edges to build in_degree, one pass over the n nodes to collect the roots.
Space
O(n)
  • The in_degree array and the result list are both sized to n.
FIG. 1557 MIN VERTICES DEGREE● INTERACTIVE
visualization loads as you reach it
class Solution:
def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
in_degree = [0] * (n)
result = []
for a, b in edges:
in_degree[b] += 1
for i in range(n):
if in_degree[i] == 0:
result.append(i)
return result

Greedy Elimination​

Both model "the one node everyone points at, that points at no one" - but instead of counting degrees, they walk the nodes once with a running candidate, discarding it whenever the current node disproves it. One survivor is left after a single pass.

2923. Find Champion I​

Easy·
2 Approachesclick to switch
Explanation

grid[i][j] == 1 is a directed edge i -> j meaning team i beats team j. A champion beats every other team, so its win count - in_degree[i] in the code, one increment per grid[i][j] == 1 - must equal n - 1. Scan every ordered pair to build the count array, then scan it for the team with n - 1 wins.

Analysis
Time
O(n + n^2)
  • The nested loop over i and j checks every ordered pair to build in_degree - O(n^2).
  • A second, separate pass over in_degree looks for the entry equal to n - 1 - O(n).
Space
O(n)
  • in_degree is a count array of size n.
FIG. 2417 FIND CHAMPION I SCAN● INTERACTIVE
visualization loads as you reach it
class Solution:
def findChampion(self, grid: List[List[int]]) -> int:
n = len(grid)
in_degree = [0 for _ in range(n)]
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
in_degree[i] += 1
for i, deg in enumerate(in_degree):
if deg == n - 1:
return i
return -1

277. Find the Celebrity​

Medium·
2 Approachesclick to switch
Explanation

Model knows(a, b) as a directed edge a -> b. The celebrity is the one node everyone else points to (in-degree n - 1) that points to no one (out-degree 0) - exactly the town-judge condition, except the trust pairs are replaced by n * (n - 1) calls to the knows API. Probe every ordered pair (i, j) with i != j, accumulate both degree arrays, then scan for the node satisfying both conditions.

This is correct but wasteful: it makes the full O(n^2) set of knows calls even though the answer can be found with far fewer.

Analysis
Time
O(n + n^2)
  • The nested loop over every ordered pair (i, j) calls knows O(n^2) times to fill both degree arrays, then a separate O(n) scan looks for the node satisfying both degree conditions - n + n^2.
Space
O(2n)
  • in_degrees and out_degrees are each a separate array of size n - 2n.
FIG. 277 FIND THE CELEBRITY DEGREE● INTERACTIVE
visualization loads as you reach it
class Solution:
def findCelebrity(self, n: int) -> int:
in_degrees = [0] * (n + 1)
out_degrees = [0] * (n + 1)
for i in range(n):
for j in range(n):
if i == j:
continue
edge = knows(i, j)
in_degrees[j] += edge
out_degrees[i] += edge
for i in range(n):
if in_degrees[i] == n - 1 and out_degrees[i] == 0:
return i
return -1

Degree Arithmetic​

Combine degrees across multiple nodes, correcting for edges shared between them.

1615. Maximal Network Rank​

Medium·
Explanation

The rank of a pair of cities (a, b) is the number of roads touching either one, counting a direct road between them only once. That's degree[a] + degree[b], minus 1 if a and b are directly connected (otherwise their shared road would be double-counted).

Build degree and an adjacency set (adj_list) from roads in one pass, then try every ordered pair (a, b) and take the best degree[a] + degree[b] - (b in adj_list[a]) - Python's bool subtracts as 0 or 1 directly.

Analysis
Time
O(E + n^2)
  • Building degree and adj_list is O(E).
  • Checking every ordered pair (a, b) is O(n^2), each with an O(1) set lookup.
Space
O(n + E)
  • The degree array is O(n); adj_list stores each edge twice, O(E).
FIG. 1615 MAXIMAL NETWORK RANK● INTERACTIVE
visualization loads as you reach it
class Solution:
def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
degree = [0] * n
adj_list = collections.defaultdict(set)
maxi = 0
for a, b in roads:
degree[a] += 1
degree[b] += 1
adj_list[a].add(b)
adj_list[b].add(a)
 
for a in range(n):
for b in range(n):
if a == b:
continue
total = degree[a] + degree[b] - (b in adj_list[a])
maxi = max(maxi, total)
return maxi