Maximal Network Rank: Graph Degree Counting

You are given n cities numbered from 0 to n - 1 and an array roads where each roads[i] = [a, b] means there is a bidirectional road between cities a and b. The network rank of two different cities is the total number of roads directly connected to either city. If a road connects both of them, it is only counted once. Return the maximal network rank of any pair of different cities.

This is LeetCode 1615: Maximal Network Rank, and it comes down to a clean observation about node degrees in an undirected graph.

Why this problem matters

Maximal Network Rank teaches you to think about graphs in terms of degree, which is the number of edges connected to a node. Degree counting is one of the most fundamental graph concepts, and it shows up in problems about connectivity, centrality, and network importance. Unlike traversal problems where you walk through the graph with DFS or BFS, this problem asks you to reason about the graph's structure at a higher level.

It is also a good exercise in translating a word problem into a formula. Once you realize that "network rank" is just "sum of degrees minus shared edge," the code practically writes itself.

The key insight

For any pair of cities (i, j), the network rank equals degree[i] + degree[j], but if there is a road directly between i and j, that road gets counted in both degrees. You need to subtract 1 to avoid double-counting.

So the formula is:

• rank(i, j) = degree[i] + degree[j] - (1 if road exists between i and j, else 0)

You need a way to quickly check whether two cities share a direct road. An adjacency set gives you O(1) lookup.

The solution

def maximal_network_rank(n: int, roads: list[list[int]]) -> int:
    degree = [0] * n
    connected = set()

    for a, b in roads:
        degree[a] += 1
        degree[b] += 1
        connected.add((a, b))
        connected.add((b, a))

    max_rank = 0
    for i in range(n):
        for j in range(i + 1, n):
            rank = degree[i] + degree[j]
            if (i, j) in connected:
                rank -= 1
            max_rank = max(max_rank, rank)

    return max_rank

First, you build a degree array by iterating through all roads. Each road increments the degree of both endpoints. At the same time, you store every road in a set (in both directions) so you can check connectivity in O(1).

Then you try every pair (i, j) where i is less than j. For each pair, compute the network rank using the formula. If the pair shares a direct road, subtract 1. Track the maximum across all pairs.

Visual walkthrough

Complexity analysis

Time: Building the degree array and adjacency set takes O(E) where E is the number of roads. Iterating over all pairs of cities takes O(n^2). Total is O(n^2 + E). Since E can be at most n*(n-1)/2, the dominant term is O(n^2).

Space: The degree array uses O(n). The connected set stores up to 2E entries, so O(E). Total is O(n + E).

The building blocks

1. Degree counting

Counting the number of edges incident to each node:

degree = [0] * n
for a, b in edges:
    degree[a] += 1
    degree[b] += 1

This is the most basic graph metric. A node's degree tells you how "connected" it is. In this problem, degree directly drives the answer. In other problems, degree helps you identify leaves (degree 1), isolated nodes (degree 0), or hubs (high degree). You will see degree counting reappear in problems like minimum height trees (peeling leaves) and Euler path detection (checking odd/even degrees).

2. Adjacency set for O(1) edge lookup

Storing edges in a set for constant-time connectivity checks:

connected = set()
for a, b in edges:
    connected.add((a, b))
    connected.add((b, a))

An adjacency list tells you "which nodes does this node connect to?" and requires scanning the neighbor list to check a specific pair. An adjacency set answers "are these two nodes connected?" in O(1). When you need both neighbor iteration and pair-checking, you can maintain both structures. In this problem, you only need the set because you never iterate over a node's neighbors.

Edge cases

• No roads: roads = []. Every city has degree 0, so the maximal network rank is 0 for any pair.
• Two cities, one road: n = 2, roads = [[0, 1]]. Only one pair exists. Rank = 1 + 1 - 1 = 1.
• Complete graph: Every pair of cities is connected. For any pair (i, j), both have degree n - 1, and they always share an edge. Rank = (n - 1) + (n - 1) - 1 = 2n - 3.
• Star graph: One central node connected to all others. The central node has degree n - 1, every leaf has degree 1. Best pair is the center with any leaf: (n - 1) + 1 - 1 = n - 1.
• Disconnected cities: Some cities have no roads. Pairs involving zero-degree cities will never produce the maximum unless all cities are isolated.

From understanding to recall

The formula degree[i] + degree[j] - shared_edge is simple, but the details matter. You need to remember to store edges in both directions, to iterate pairs with j > i to avoid duplicates, and to handle the subtraction correctly. Under interview pressure, it is easy to forget the subtraction or to use an adjacency list when a set would be cleaner.

Spaced repetition helps you internalize these small decisions. After a few rounds of writing the degree-counting loop and the pair-checking loop from scratch, the pattern becomes automatic. You stop thinking about whether to subtract 0 or 1, because your hands already know.

Related posts

• Course Schedule - Graph traversal with adjacency lists, a natural next step after learning degree counting
• Clone Graph - Graph representation and traversal, building comfort with adjacency structures
• Number of Islands - Graph exploration fundamentals, the entry point for thinking about connected components

Graph problems get easier once you stop seeing them as a category and start seeing them as combinations of small building blocks. Degree counting, adjacency sets, DFS, BFS: each one is a small, learnable piece. Maximal Network Rank uses two of those pieces and nothing else.