Maximal Network Rank — Solution in Python, Java & C++
Maximal Network Rank solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on graph.
Maximal Network Rank is a medium coding problem on graph, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Graph
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n cities numbered 0 through n - 1, joined by bidirectional roads. The network rank of two different cities is the number of roads directly connected to either one, where a road linking the two counts only once.
Return the maximum network rank over all pairs of cities.
Example 1
Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Example 2
Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Example 3
Input: n = 2, roads = []
Output: 0
Constraints
2 <= n <= 400 <= roads.length <= 60There are no duplicate roads and no self-loops.
Hints for Maximal Network Rank
Hint 1
The rank of a pair is
degree[a] + degree[b], minus one if they share a road.Hint 2
Count degrees first and store the road set for O(1) adjacency lookups.
Hint 3
Then try every pair — with these bounds the quadratic scan is plenty fast.
How to solve Maximal Network Rank
The rank of a pair is deg[a] + deg[b], minus one if they are directly connected; compute degrees and a road set, then scan all pairs.
Approach
- Count degrees and store each road as an unordered pair in a set.
- For every pair, compute the rank and track the maximum.
Why it works
Roads incident to either city are counted by the degree sum, with the shared road counted twice and corrected once.
Complexity
- Time —
O(n² + r) - Space —
O(r)
Pitfalls
- The quadratic pair scan is fine at
n ≤ 100.
Reference solution
Python
def maximalNetworkRank(n: int, roads) -> int:
degree = [0] * n
connected = set()
for a, b in roads:
degree[a] += 1
degree[b] += 1
connected.add((min(a, b), max(a, b)))
best = 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
best = max(best, rank)
return bestJava
public static int maximalNetworkRank(int n, int[][] roads) {
int[] degree = new int[n];
boolean[][] connected = new boolean[n][n];
for (int[] road : roads) {
degree[road[0]]++;
degree[road[1]]++;
connected[road[0]][road[1]] = true;
connected[road[1]][road[0]] = true;
}
int best = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int rank = degree[i] + degree[j];
if (connected[i][j]) rank--;
best = Math.max(best, rank);
}
}
return best;
}C++
int maximalNetworkRank(int n, vector<vector<int>>& roads) {
vector<int> degree(n, 0);
vector<vector<bool>> connected(n, vector<bool>(n, false));
for (const auto& road : roads) {
degree[road[0]]++;
degree[road[1]]++;
connected[road[0]][road[1]] = true;
connected[road[1]][road[0]] = true;
}
int best = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int rank = degree[i] + degree[j];
if (connected[i][j]) rank--;
best = max(best, rank);
}
}
return best;
}JavaScript
var maximalNetworkRank = function(n, roads) {
const degree = [];
for (let i = 0; i < n; i++) degree.push(0);
const connected = new Set();
for (let i = 0; i < roads.length; i++) {
const a = roads[i][0], b = roads[i][1];
degree[a]++;
degree[b]++;
connected.add(a < b ? a + "," + b : b + "," + a);
}
let best = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
let rank = degree[i] + degree[j];
if (connected.has(i + "," + j)) rank--;
if (rank > best) best = rank;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 107 graph problems · the whole catalogue
Learn the technique: Graph Data Structure