Maximal Network Rank

medium graph

Problem

You have n cities (0..n-1) and a list of bidirectional roads. The network rank of two different cities is the total number of roads connected to either, counting a shared road only once. Return the maximal network rank over all pairs.

Inputn = 4, roads = [[0,1],[0,3],[1,2],[1,3]]

Output4

Pair (0,1) sums to deg 2+3=5 minus 1 shared road = 4.

roads (JSON)

def maximal_network_rank(n, roads):
    deg = [0] * n
    connected = set()
    for a, b in roads:
        deg[a] += 1
        deg[b] += 1
        connected.add((min(a, b), max(a, b)))
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            r = deg[i] + deg[j] - ((i, j) in connected)
            if r > best: best = r
    return best

function maximalNetworkRank(n, roads) {
  const deg = new Array(n).fill(0);
  const connected = new Set();
  for (const [a, b] of roads) {
    deg[a]++; deg[b]++;
    connected.add(Math.min(a, b) + "," + Math.max(a, b));
  }
  let best = 0;
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++) {
      const r = deg[i] + deg[j] - (connected.has(i + "," + j) ? 1 : 0);
      if (r > best) best = r;
    }
  return best;
}

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        int[] deg = new int[n];
        boolean[][] adj = new boolean[n][n];
        for (int[] r : roads) {
            deg[r[0]]++; deg[r[1]]++;
            adj[r[0]][r[1]] = true; adj[r[1]][r[0]] = true;
        }
        int best = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int r = deg[i] + deg[j] - (adj[i][j] ? 1 : 0);
                if (r > best) best = r;
            }
        return best;
    }
}

int maximalNetworkRank(int n, vector<vector<int>>& roads) {
    vector<int> deg(n, 0);
    vector<vector<bool>> adj(n, vector<bool>(n, false));
    for (auto& r : roads) {
        deg[r[0]]++; deg[r[1]]++;
        adj[r[0]][r[1]] = adj[r[1]][r[0]] = true;
    }
    int best = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int r = deg[i] + deg[j] - (adj[i][j] ? 1 : 0);
            if (r > best) best = r;
        }
    return best;
}

Explanation

The network rank of two cities is just how many roads touch either of them. The only catch: a road directly between the two should be counted once, not twice.

So we first count the degree of every city in deg (how many roads each one has) and record which pairs share a direct road in a set called connected.

Then we try every pair (i, j). Their rank is deg[i] + deg[j], but if that exact pair is in connected we subtract 1 for the shared road. We keep the largest value in best.

Why subtract one? If a road runs between i and j, it was counted in both degrees, so naively adding double-counts it.

Example: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]. City 0 has degree 2, city 1 has degree 3, and they share a road, so their rank is 2 + 3 - 1 = 4, which is the maximum.

Time: O(n² + E) Space: O(n + E)