Maximal Network Rank

LeetCode 1738 | Difficulty: Medium

Medium

Problem Description

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [a~i~, b~i~] indicates that there is a bidirectional road between cities a~i~ and b~i~.

The network rank* *of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

Example 1:

Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Example 2:

Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.

Example 3:

Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.

Constraints:

- `2 <= n <= 100`

- `0 <= roads.length <= n * (n - 1) / 2`

- `roads[i].length == 2`

- `0 <= a~i~, b~i~ <= n-1`

- `a~i~ != b~i~`

- Each pair of cities has **at most one** road connecting them.

Topics: Graph Theory

---

Approach

Graph Traversal

Model the problem as a graph (nodes + edges). Choose BFS for shortest path or DFS for exploring all paths. For dependency ordering, use topological sort (Kahn's BFS or DFS with finish times).

When to use

Connectivity, shortest path, cycle detection, dependency ordering.

---

Solutions

Solution 1: C# (Best: 223 ms)

Metric	Value
Runtime	223 ms
Memory	41.2 MB
Date	2022-02-08

Solution

public class Solution {
    public int MaximalNetworkRank(int n, int[][] roads) {
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
    foreach(int[] road in roads)
    {
        if(graph.ContainsKey(road[0]))
        {
            graph[road[0]].Add(road[1]);            
        }
        else graph.Add(road[0], new List<int>() { road[1]});

        if (graph.ContainsKey(road[1]))
        {
            graph[road[1]].Add(road[0]);
        }
        else graph.Add(road[1], new List<int>() { road[0] });
    }
    
    int max = 0;
    for (int i = 0; i < n-1; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            if(graph.ContainsKey(i) && graph.ContainsKey(j))
            max = Math.Max(max, graph[i].Count+graph[j].Count-(graph[i].Contains(j) ? 1 : 0));
        }
    }
    
    return max;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask about graph properties: directed/undirected, weighted/unweighted, cycles, connectivity.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Try every pair of different cities and calculate its network rank.

Hint 2: The network rank of two vertices is almost the sum of their degrees.

Hint 3: How can you efficiently check if there is a road connecting two different cities?