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:

1
2
3

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
  
1
2
3

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:

1
2
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

  1. Initialize an array to store the degree (number of roads) for each city.
  2. Use a set to store all direct connections (edges) for quick lookup.
  3. For each road, increment the degree for both cities and add the edge to the set (in both orders for easy lookup).
  4. 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.
  5. Return the maximal network rank found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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.