Maximal Network Rank
MediumUpdated: Aug 2, 2025
Practice on:
Problem
There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.
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.
Examples
graph LR; 0:::ans_node --- 1 & 3; 1:::ans_node --- 2 & 3; classDef ans_node fill:#3B1 linkStyle 0 stroke-width:4px,stroke:green linkStyle 1 stroke-width:4px,stroke:green linkStyle 2 stroke-width:4px,stroke:green linkStyle 3 stroke-width:4px,stroke:green
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:
graph LR; 0 --- 1 & 3; 1:::ans_node --- 2 & 3; 2:::ans_node --- 3 & 4; classDef ans_node fill:#3B1 linkStyle 2 stroke-width:4px,stroke:green linkStyle 3 stroke-width:4px,stroke:green linkStyle 4 stroke-width:4px,stroke:green linkStyle 5 stroke-width:4px,stroke:green
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.
Solution
Method 1 – Degree Counting and Edge Set
Intuition
The key idea is that the network rank for any pair of cities is the sum of their degrees (number of roads connected to each) minus one if they are directly connected (since the shared road is counted twice). By counting degrees and using a set to check direct connections, we can efficiently compute the maximal network rank.
Approach
- Initialize an array to store the degree (number of roads) for each city.
- Use a set to store all direct connections (edges) for quick lookup.
- For each road, increment the degree for both cities and add the edge to the set (in both orders for easy lookup).
- Iterate over all pairs of different cities (i, j):
- Compute the sum of their degrees.
- If they are directly connected, subtract one.
- Track the maximum value found.
- Return the maximal network rank found.
Code
C++
class Solution {
public:
int maximalNetworkRank(int n, vector<vector<int>>& roads) {
vector<int> deg(n);
unordered_set<int> st;
for (auto& r : roads) {
deg[r[0]]++;
deg[r[1]]++;
st.insert(r[0] * 100 + r[1]);
st.insert(r[1] * 100 + r[0]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int cur = deg[i] + deg[j];
if (st.count(i * 100 + j)) cur--;
ans = max(ans, cur);
}
}
return ans;
}
};
Go
func maximalNetworkRank(n int, roads [][]int) int {
deg := make([]int, n)
st := make(map[[2]int]bool)
for _, r := range roads {
deg[r[0]]++
deg[r[1]]++
st[[2]int{r[0], r[1]}] = true
st[[2]int{r[1], r[0]}] = true
}
ans := 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
cur := deg[i] + deg[j]
if st[[2]int{i, j}] {
cur--
}
if cur > ans {
ans = cur
}
}
}
return ans
}
Java
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
int[] deg = new int[n];
Set<String> st = new HashSet<>();
for (int[] r : roads) {
deg[r[0]]++;
deg[r[1]]++;
st.add(r[0] + "," + r[1]);
st.add(r[1] + "," + r[0]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int cur = deg[i] + deg[j];
if (st.contains(i + "," + j)) cur--;
ans = Math.max(ans, cur);
}
}
return ans;
}
}
Kotlin
class Solution {
fun maximalNetworkRank(n: Int, roads: Array<IntArray>): Int {
val deg = IntArray(n)
val st = mutableSetOf<Pair<Int, Int>>()
for (r in roads) {
deg[r[0]]++
deg[r[1]]++
st.add(Pair(r[0], r[1]))
st.add(Pair(r[1], r[0]))
}
var ans = 0
for (i in 0 until n) {
for (j in i + 1 until n) {
var cur = deg[i] + deg[j]
if (st.contains(Pair(i, j))) cur--
ans = maxOf(ans, cur)
}
}
return ans
}
}
Python
class Solution:
def maximalNetworkRank(self, n: int, roads: list[list[int]]) -> int:
deg = [0] * n
st = set()
for a, b in roads:
deg[a] += 1
deg[b] += 1
st.add((a, b))
st.add((b, a))
ans = 0
for i in range(n):
for j in range(i + 1, n):
cur = deg[i] + deg[j]
if (i, j) in st:
cur -= 1
ans = max(ans, cur)
return ans
Rust
impl Solution {
pub fn maximal_network_rank(n: i32, roads: Vec<Vec<i32>>) -> i32 {
let n = n as usize;
let mut deg = vec![0; n];
let mut st = std::collections::HashSet::new();
for r in &roads {
deg[r[0] as usize] += 1;
deg[r[1] as usize] += 1;
st.insert((r[0], r[1]));
st.insert((r[1], r[0]));
}
let mut ans = 0;
for i in 0..n {
for j in i + 1..n {
let mut cur = deg[i] + deg[j];
if st.contains(&(i as i32, j as i32)) {
cur -= 1;
}
ans = ans.max(cur);
}
}
ans
}
}
TypeScript
class Solution {
maximalNetworkRank(n: number, roads: number[][]): number {
const deg = Array(n).fill(0);
const st = new Set<string>();
for (const [a, b] of roads) {
deg[a]++;
deg[b]++;
st.add(`${a},${b}`);
st.add(`${b},${a}`);
}
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
let cur = deg[i] + deg[j];
if (st.has(`${i},${j}`)) cur--;
ans = Math.max(ans, cur);
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n^2), because we check all pairs of cities (i, j) where i < j, and each lookup in the set is O(1). - 🧺 Space complexity:
O(n + m), where n is the number of cities and m is the number of roads, for the degree array and the set of edges.