Watch 10 video solutions for Maximal Network Rank, a medium level problem involving Graph. This walkthrough by Naresh Gupta has 11,036 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.
Example 1:
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.
Example 2:
Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]] Output: 5 Explanation: There are 5 roads that are connected to cities 1 or 2.
Example 3:
Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]] Output: 5 Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.
Constraints:
2 <= n <= 1000 <= roads.length <= n * (n - 1) / 2roads[i].length == 20 <= ai, bi <= n-1ai != biProblem Overview: You are given n cities connected by bidirectional roads. The network rank of two cities is the total number of roads connected to either city, counting a shared road only once. The task is to compute the maximum network rank across every pair of cities.
Approach 1: Degree Counting and Direct Road Check (O(n^2) time, O(n + m) space)
This approach relies on a key observation: the network rank of two cities u and v equals degree[u] + degree[v], minus one if a direct road connects them. Start by iterating through the road list and building a degree array that counts how many roads touch each city. Store each road in a hash-based structure such as a set for constant-time connection checks. Then iterate over every pair of cities (i, j), compute the candidate rank using their degrees, and subtract one if the pair shares a direct road.
This works because the degree already represents total incident roads, so combining two degrees counts all roads touching either city. The only double-count occurs when both cities share the same road, which the direct lookup fixes. The approach scans all city pairs, giving O(n^2) time after preprocessing. It uses O(n + m) space for the degree array and road set. This pattern is common in graph problems where node degrees provide quick relationship metrics.
Approach 2: Adjacency Matrix Based Calculation (O(n^2) time, O(n^2) space)
An alternative implementation uses an adjacency matrix to represent connectivity between cities. Create an n x n boolean matrix where matrix[u][v] is true if a road exists. While building the matrix, maintain the same degree array used in the previous approach. Once constructed, iterate through every pair of cities and compute the network rank as degree[i] + degree[j], subtracting one if matrix[i][j] is true.
The adjacency matrix allows constant-time connection checks without hashing, which can simplify the implementation in languages like Java or C#. The tradeoff is memory usage: storing the full matrix requires O(n^2) space. For dense graphs or small constraints, this representation is straightforward and efficient. This technique is widely used in graph algorithms and is a standard representation for problems involving frequent edge lookups, often referred to as an adjacency matrix.
Recommended for interviews: Degree counting with a direct road lookup is the approach most interviewers expect. It shows you recognize the degree property of graph nodes and can optimize pair calculations with constant-time edge checks. A brute-force interpretation of counting all roads per pair demonstrates understanding, but the degree-based method demonstrates stronger graph reasoning and cleaner implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Degree Counting + Direct Road Check | O(n^2 + m) | O(n + m) | General case with sparse graphs; memory efficient and commonly used in interviews |
| Adjacency Matrix Calculation | O(n^2) | O(n^2) | When constant-time edge lookup is preferred and n is small enough for matrix storage |