Skip to main content
Talentd

Maximal Network Rank - Solution & Explanation

MediumGraph12 min readAsked at: Microsoft
Practice this problem

Problem Statement

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 <= 100
  • 0 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 2
  • 0 <= ai, bi <= n-1
  • ai != bi
  • Each pair of cities has at most one road connecting them.

Approach Overview

Problem 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 1: Degree Counting and Direct Road Check

This approach involves counting the number of roads connected to each city and then checking directly connected pairs to maximize the network rank. For each pair of cities, calculate their combined road count and subtract one if there is a direct road between the two cities since that road is counted twice.

We use an array to store how many roads connect to each city. For two cities, we sum their connections and subtract one if there is a direct road between them, ensuring the road isn't counted twice. We check each possible pair to find the maximal rank.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(|E| + n2), where |E| is the number of roads and n is the number of cities.
Space Complexity: O(n), for storing road counts and direct connection set.

Try this approach in the editor →

Approach 2: Adjacency Matrix Based Calculation

This approach utilizes an adjacency matrix to track connections between cities and then computes the maximal network rank by leveraging matrix operations. This can be particularly useful when sparsity is high and offers constant time complexity for checking direct connections.

An adjacency matrix allows quick checks of direct connections between cities. We leverage the matrix to ensure we only count roads once for directly connected city pairs. Each pair of cities is evaluated to find the maximal rank.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n2)
Space Complexity: O(n2), due to the adjacency matrix.

Try this approach in the editor →

Approach 3: Counting

We can use a one-dimensional array cnt to record the degree of each city and a two-dimensional array g to record whether there is a road between each pair of cities. If there is a road between city a and city b, then g[a][b] = g[b][a] = 1; otherwise, g[a][b] = g[b][a] = 0.

Next, we enumerate each pair of cities (a, b), where a \lt b, and calculate their network rank, which is cnt[a] + cnt[b] - g[a][b]. The maximum value among these is the answer.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the number of cities.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Degree Counting and Direct Road Check

Time Complexity: O(|E| + n2), where |E| is the number of roads and n is the number of cities.
Space Complexity: O(n), for storing road counts and direct connection set.

Adjacency Matrix Based Calculation

Time Complexity: O(n2)
Space Complexity: O(n2), due to the adjacency matrix.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Degree Counting + Direct Road CheckO(n^2 + m)O(n + m)General case with sparse graphs; memory efficient and commonly used in interviews
Adjacency Matrix CalculationO(n^2)O(n^2)When constant-time edge lookup is preferred and n is small enough for matrix storage

Video Solution

Maximal Network Rank | Simple and Straight | 2 Ways | MICROSOFT | Leetcode-239 | Dry Run | Live Code • codestorywithMIK • 8,788 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximal Network Rank easy or hard?
Maximal Network Rank is classified as a medium-level problem. The logic is straightforward once you recognize that node degrees represent the number of connected roads, but you must handle the case where the two cities share a direct road.
Maximal Network Rank Python/Java solution
In Python, the common implementation uses a degree list and a set of road tuples for O(1) connectivity checks. In Java, many solutions use either a HashSet for edges or a boolean adjacency matrix along with an integer degree array.
How to solve Maximal Network Rank in O(n)?
An exact O(n) solution is not practical because the algorithm must consider pairs of cities to determine the maximum network rank. The optimal strategy reduces the work to O(n^2) pair checks using precomputed degrees and constant-time road lookups.
What is the best approach for Maximal Network Rank?
The most efficient and commonly expected solution uses degree counting with a constant-time check for direct roads. Compute the degree of each city, then evaluate every pair of cities using degree[u] + degree[v] and subtract one if they share a road. This runs in O(n^2 + m) time and uses O(n + m) space.
Is Maximal Network Rank asked at Google/Amazon/Meta?
Graph problems involving node degrees and pair evaluation frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact question may vary, the concept of combining node degrees and handling shared edges is a common interview pattern.
What data structure is used in Maximal Network Rank?
The solution typically uses a degree array to store the number of roads per city and either a hash set or an adjacency matrix to check whether two cities are directly connected. These structures allow constant-time lookups during pair evaluation.
What is the time complexity of Maximal Network Rank?
Most optimal implementations run in O(n^2 + m) time. Building the degree array from the road list takes O(m), and checking all city pairs requires O(n^2). Space complexity is O(n + m) with a set-based road lookup or O(n^2) with an adjacency matrix.

Ready to solve this problem?

Practice Maximal Network Rank with our built-in code editor and test cases.

Practice on FleetCode
Previous

Clone Graph

Next

Course Schedule