Maximal Network Rank

Maximal Network Rank

What is this problem about?

The Maximal Network Rank problem gives you an integer n (number of cities) and an array of roads connecting them. The "network rank" of any two distinct cities is the total number of roads directly connected to either city. If a road directly connects the two cities, it should only be counted once. Your goal is to find the maximum network rank out of all possible pairs of cities.

Why is this asked in interviews?

This is a straightforward Graph problem. Interviewers use it to verify that a candidate understands basic graph properties like nodes, edges, and degrees. It is an excellent test of whether a candidate can build an adjacency list or matrix and accurately handle the "intersection" logic (avoiding double-counting a shared edge).

Algorithmic pattern used

This utilizes Graph Degree Counting and Nested Iteration. Because n is small (typically up to 100), an $O(N^2)$ traversal of all city pairs is perfectly optimal.

1. Build an array to store the "degree" (number of connected roads) for each city.
2. Build an adjacency matrix (a 2D boolean array) or Hash Set to quickly check if an edge exists between two specific cities.
3. Iterate through every possible pair of cities (i, j). The network rank is degree[i] + degree[j]. If the adjacency matrix indicates they are connected, subtract 1 to avoid double-counting. Track the global maximum.

Example explanation

4 cities, roads: [[0,1], [0,3], [1,2], [1,3]].

1. Calculate degrees:

• City 0: 2 roads
• City 1: 3 roads
• City 2: 1 road
• City 3: 2 roads

1. Check pairs:

• Pair (0, 1): degree[0] + degree[1] = $2 + 3 = 5$. They are connected, so subtract 1. Rank = 4.
• Pair (1, 3): degree[1] + degree[3] = $3 + 2 = 5$. They are connected. Subtract 1. Rank = 4.
• Pair (0, 2): degree[0] + degree[2] = $2 + 1 = 3$. They are NOT connected. Subtract 0. Rank = 3. The maximum network rank is 4.

Common mistakes candidates make

A common error is trying to find the two cities with the absolute highest degrees and assuming their combined rank is the answer. This greedy assumption fails! Two cities with slightly lower degrees that are not connected might yield a higher network rank than two top-degree cities that are connected. You must check every pair. Another mistake is using a slow adjacency list lookup instead of a fast $O(1)$ adjacency matrix, causing unnecessary slowdowns.

Interview preparation tip

For the Maximal Network Rank coding problem, immediately declare an int[] counts for the node degrees and a boolean[][] connected for the adjacency matrix. This setup takes 5 lines of code and reduces the core logic to a trivial double-for-loop. It is a highly reliable template for dense graph comparison problems.