[/dsa/leetcode]

1615 - Maximal Network Rank

Tuesday, 8 September 2026

<medium> [problem]

The rank of a pair is the union of their edge sets, so it is the sum of two degrees minus one when the pair is joined by a road.

{graph}

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. Return the maximal network rank of the entire infrastructure.

Network Rank

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.

Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5

Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The highest network rank does not have to be between directly connected cities.

Approach

“Roads directly connected to a city” is just that city’s degree, so the first move is to stop thinking about roads and start thinking about per-node counts.

The whole problem lives in the “only counted once” clause. The rank of a pair is the size of the union of the two edge sets, not the sum of two counts:

rank(u, v) = |edges(u) ∪ edges(v)| = deg(u) + deg(v) - |edges(u) ∩ edges(v)|

Those two sets can overlap in exactly one place — the road between u and v itself. There are no self loops and no repeated roads, so the intersection has size 1 when u and v are adjacent and 0 otherwise. Inclusion–exclusion at the smallest possible scale:

rank(u, v) = deg(u) + deg(v) - (adjacent(u, v) ? 1 : 0)

That penalty is what makes the problem more than a max-of-degrees exercise, and it is the source of both common bugs: adding degrees everywhere (overcounts adjacent pairs) or subtracting 1 from every pair (undercounts the non-adjacent ones).

Two structures fall out of the formula — degrees, and an adjacency test that answers “are these two directly connected?” for a given pair. Both need to be cheap.

Brute force over pairs

Build an adjacency list, then walk every pair and apply the formula, checking adjacency by scanning the neighbour list.

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        unordered_map<int, vector<int>> mp;
        for(auto it : roads) {
            mp[it[0]].push_back(it[1]);
            mp[it[1]].push_back(it[0]);
        }
        int ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1;j < n; j++) {
                int t = mp[i].size() + mp[j].size();
                if(find(mp[i].begin(), mp[i].end(), j) != mp[i].end()) {
                    t--;
                }
                ans = max(ans, t);
            }
        }
        return ans;
    }
};

This is correct and passes, but the find is a linear scan of i’s neighbour list done once per pair, which drags an O(1) step up to O(deg(i)). The pair loop is only n² = 10⁴ iterations; the adjacency checks push the real work to roughly n × Σdeg(i) = n × 2E ≈ 10⁶.

  • time: O(n · E) — n² pairs, each scanning a neighbour list
  • space: O(n + E) — the adjacency list

The unordered_map is also the wrong container here. The keys are dense 0..n-1, so every mp[i] inside the hot loop pays for hashing, and operator[] silently inserts empty vectors for isolated cities. A plain vector indexed by city is strictly better.

Adjacency matrix

Keep degrees and adjacency as two separate structures so the inner body is genuinely constant time. n ≤ 100, so an n × n matrix is tiny.

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        vector<int> deg(n, 0);
        vector<vector<bool>> adj(n, vector<bool>(n, false));
        for(const auto& road : roads) {
            deg[road[0]]++;
            deg[road[1]]++;
            adj[road[0]][road[1]] = adj[road[1]][road[0]] = true;
        }

        int ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                ans = max(ans, deg[i] + deg[j] - adj[i][j]);
            }
        }
        return ans;
    }
};

adj[i][j] is a bool that promotes to 0 or 1, so the penalty needs no branch. This is the expected solution — same shape as the brute force, with the linear scan replaced by a table lookup.

  • time: O(n² + E) — one pass over the edges, one pass over the pairs
  • space: O(n²) — the matrix

Two largest degrees

Every pair does not need to be examined. Let first be the largest degree and second the next largest. Since the penalty is at most 1, the answer can only come from the top of the degree ordering:

  • Two or more cities tie for first. If any two of them are not directly connected the answer is 2 * first, otherwise every such pair pays the penalty and the answer is 2 * first - 1. No mixed pair can beat that, because every other degree is at most first, so any other pair scores at most first + second ≤ 2 * first - 1 when second < first, and is itself a top pair when second == first.
  • Exactly one city u has degree first. Its partner is some city of degree second. The answer is first + second, minus 1 only if u is adjacent to every city of degree second.
class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        vector<int> deg(n, 0);
        unordered_set<int> edge;
        for(const auto& road : roads) {
            deg[road[0]]++;
            deg[road[1]]++;
            edge.insert(road[0] * n + road[1]);
            edge.insert(road[1] * n + road[0]);
        }

        int first = 0, second = 0;
        for(int d : deg) {
            if(d > first) { second = first; first = d; }
            else if(d > second) second = d;
        }

        vector<int> top, nxt;
        for(int i = 0; i < n; i++) {
            if(deg[i] == first) top.push_back(i);
            else if(deg[i] == second) nxt.push_back(i);
        }

        if(top.size() >= 2) {
            for(size_t i = 0; i < top.size(); i++) {
                for(size_t j = i + 1; j < top.size(); j++) {
                    if(!edge.count(top[i] * n + top[j])) return 2 * first;
                }
            }
            return 2 * first - 1;
        }

        for(int v : nxt) {
            if(!edge.count(top[0] * n + v)) return first + second;
        }
        return first + second - 1;
    }
};

The pair (u, v) is encoded as u * n + v in a hash set, both directions, which gives O(1) adjacency without the n² matrix.

The nested loop over top looks like it reintroduces O(n²), but it only runs long when the max-degree cities are mutually adjacent — and a clique of size k already forces E ≥ k(k-1)/2, so that scan stays bounded by the edge count.

  • time: O(n + E)
  • space: O(n + E) — the degree array and the edge set

At n ≤ 100 this buys nothing over the matrix and has three edge cases to get wrong (a single max node, all degrees equal, and an empty roads). It is worth understanding because it is the answer to “what if n were 10⁵”, and because working out why the two highest-degree cities are not automatically the answer is the real content of the problem.

quantinium © 2026