1615. Maximal Network Rank

Problem¶

Given n cities labeled 0 to n - 1 and an undirected list of roads, find the maximum rank over all pairs of different cities.

• The rank of a pair is the number of roads touching either city.
• If a road connects the two cities directly, count it once.

Example:

n = 4
roads = [[0,1],[0,3],[1,2],[1,3]]

pair (0,1) -> roads touching 0 or 1 = {0-1, 0-3, 1-2, 1-3} -> rank = 4
answer = 4

Key trick¶

Count each city's degree first, then for every pair compute:

degree[a] + degree[b] - 1 if a and b are directly connected else degree[a] + degree[b]

Because n <= 100, checking all pairs is fast enough.

Trap¶

The common mistake is to subtract 1 for any pair, even when the cities are not directly connected.

Another trap is thinking the pair must be connected by a path; the pair only needs roads incident to either city.

Why is it interesting?¶

It is a small graph problem that tests whether you can model an "either endpoint" count correctly and handle double-counting cleanly.

Python solution¶

class Solution:
    def maximalNetworkRank(self, n: int, roads: list[list[int]]) -> int:
        degree = [0] * n
        graph = [set() for _ in range(n)]
        for a, b in roads:
            degree[a] += 1
            degree[b] += 1
            graph[a].add(b)
            graph[b].add(a)
        best = 0
        for a in range(n):
            for b in range(a + 1, n):
                adjacent = 1 if b in graph[a] else 0
                best = max(best, degree[a] + degree[b] - adjacent)
        return best

Comment on my solution¶

Your approach is correct and interview-ready.

• The degree count is the right first step.
• Using adjacency sets makes the direct-edge check simple and efficient.
• The final double loop is fine because n is small.

One minor note:

• The comment rank can be counted as sum of degrees of a and b minus 1 when a and b have a common edge is correct only when the pair is directly connected.
• Your later code already handles this properly, so the implementation is good.

# Ideas:
# - rank can be counted as sum of degrees of a and b minus 1 when a and b
#   have a common edge
#   - wrong: I misread the problem. roads a and b don't have to be connected

# WORKS
class Solution:
    def maximalNetworkRank(self, n: int, roads: list[list[int]]) -> int:
        degree = [0] * n
        graph = [set() for _ in range(n)]
        for a, b in roads:
            degree[a] += 1
            degree[b] += 1
            graph[a].add(b)
            graph[b].add(a)
        best = 0
        for a in range(n):
            for b in range(a + 1, n):
                adjacent = 1 if b in graph[a] else 0
                best = max(best, degree[a] + degree[b] - adjacent)
        return best