Problem 20.5 · Graph FundamentalsMedium

Maximal Network Rank

What it teaches: Degrees plus an adjacency matrix for O(1) "are these two connected?" checks.

Practise it on judges as “Maximal Network Rank”.

The problem

The network rank of two different cities is the number of roads touching either city (a road between them counts once). Return the maximum network rank over all pairs.

Example 1

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

Cities 0 and 1: degrees 2 + 3, minus the shared road.

Constraints

2 ≤ n ≤ 100
Each pair has at most one road

Pattern clues in the wording

→ Small n, pairs of nodes
→ Need fast edge-exists checks

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 4 roads = [[0,1],[0,3],[1,2],[1,3]]	4
2	n = 5 roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]	5
3	n = 8 roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]	5

From slow to fast

Approaches

1. Degrees + matrix, all pairs · O(n² + E)

Degrees + matrix, all pairs

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

Count degrees and fill a boolean matrix. Try every pair.

Approach 1

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        int[] deg = new int[n];
        boolean[][] connected = new boolean[n][n];
        for (int[] r : roads) {
            deg[r[0]]++; deg[r[1]]++;
            connected[r[0]][r[1]] = connected[r[1]][r[0]] = true;
        }
        int best = 0;
        for (int a = 0; a < n; a++)
            for (int b = a + 1; b < n; b++)
                best = Math.max(best, deg[a] + deg[b] - (connected[a][b] ? 1 : 0));
        return best;
    }
}

Verdict: n ≤ 100 makes the matrix the right tool.

Before you submit

Edge cases and common mistakes

Test these inputs

The two highest-degree cities are connected
No roads

Mistakes people make

Counting the shared road twice.

Interview

Follow-up questions

How would you do it for n = 10⁵?

Command Palette

The problem

Approaches

Degrees + matrix, all pairs

Edge cases and common mistakes

Follow-up questions