Maximal Network Rank

Medium
463.

Maximal Network Rank

Maximal Network Rank is a medium coding problem on graph, asked in Amazon, Google and Microsoft interviews.

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 <= 40
  • 0 <= roads.length <= 60
  • There are no duplicate roads and no self-loops.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var maximalNetworkRank = function(n, roads) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 40
  • 0 <= roads.length <= 60
  • There are no duplicate roads and no self-loops.

Hints for Maximal Network Rank

  1. Hint 1

    The rank of a pair is degree[a] + degree[b], minus one if they share a road.

  2. Hint 2

    Count degrees first and store the road set for O(1) adjacency lookups.

  3. 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

  1. Count degrees and store each road as an unordered pair in a set.
  2. 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 best

Java

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