# Maximal Network Rank
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximal-network-rank)
Canonical: https://scaleengineer.com/dsa/problems/maximal-network-rank
**Data structures:** Graph
**Companies:** [smartnews](https://scaleengineer.com/companies/smartnews), [DRW](https://scaleengineer.com/companies/drw)
---
## 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.

Given the integer `n` and the array `roads`, return _the **maximal network rank** of the entire infrastructure_.

**Example 1:**

**![](https://assets.glich.co/dsa/maximal-network-rank/image0.png)**

**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:**

**![](https://assets.glich.co/dsa/maximal-network-rank/image1.png)**

**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.

# Approaches
## Naive Brute Force
This approach directly translates the problem definition into code. It iterates through every possible pair of distinct cities. For each pair, it calculates their network rank from scratch by re-iterating through the entire `roads` list to count the degrees of the two cities and to check if they are directly connected. This leads to a lot of repeated work.
**Time:** O(n² * R), where `n` is the number of cities and `R` is the number of roads. There are `O(n²)` pairs of cities. For each pair, we iterate through all `R` roads to compute degrees and check for a connection. · **Space:** O(1), as it only uses a few variables to store intermediate values and does not depend on the input size.
**Pros:** Very simple to conceptualize and implement.; Requires no additional space apart from a few variables.
**Cons:** Extremely inefficient due to redundant computations.; The time complexity of `O(n^2 * R)` makes it likely to exceed time limits for the given constraints.
### Explanation
The simplest way to solve the problem is to consider every single pair of different cities and calculate their network rank. The maximal network rank will be the maximum among all these calculated ranks.

To calculate the rank for a pair of cities `(i, j)`, we need two pieces of information:
1. The number of roads connected to city `i` (its degree).
2. The number of roads connected to city `j` (its degree).

In this naive approach, we calculate these degrees on-the-fly for each pair. We also need to check if a road exists directly between `i` and `j`, because if it does, it's counted in both degrees and we must subtract one to count it only once. This check is also done by scanning the `roads` list.

```java
class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        int maxRank = 0;
        // Iterate through all unique pairs of cities (i, j)
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int degree_i = 0;
                int degree_j = 0;
                
                // Calculate degrees for i and j for the current pair
                for (int[] road : roads) {
                    if (road[0] == i || road[1] == i) {
                        degree_i++;
                    }
                    if (road[0] == j || road[1] == j) {
                        degree_j++;
                    }
                }
                
                // Check if the two cities are directly connected
                boolean connected = false;
                for (int[] road : roads) {
                    if ((road[0] == i && road[1] == j) || (road[0] == j && road[1] == i)) {
                        connected = true;
                        break;
                    }
                }
                
                int currentRank = degree_i + degree_j;
                if (connected) {
                    currentRank--;
                }
                
                maxRank = Math.max(maxRank, currentRank);
            }
        }
        return maxRank;
    }
}
```
Note: The two inner loops over `roads` can be combined into one for a slight optimization, but the overall complexity remains the same.
### Algorithm
- Initialize a variable `maxRank` to 0.
- Create a nested loop to iterate through every possible unique pair of cities `(i, j)`.
- Inside the loops, for each pair `(i, j)`:
  - Initialize `degree_i = 0`, `degree_j = 0`, and a boolean `connected = false`.
  - Iterate through the entire `roads` array.
    - For each `road`, check if it's connected to city `i` or city `j` to calculate their degrees.
    - Also, check if the road directly connects `i` and `j`.
  - Calculate the `currentRank` as `degree_i + degree_j`.
  - If `i` and `j` are directly connected, subtract 1 from `currentRank`.
  - Update `maxRank` with the maximum value seen so far.
- After checking all pairs, return `maxRank`.

## Pre-computation and Brute Force
This approach significantly improves performance by pre-computing the necessary information. Before checking pairs, it makes a single pass through the `roads` list to calculate the degree of every city and to build a representation of the graph (e.g., an adjacency matrix or list) for quick connection lookups. After this pre-computation step, it iterates through all pairs of cities, but now the rank for each pair can be calculated in constant time.
**Time:** O(n² + R), where `n` is the number of cities and `R` is the number of roads. The pre-computation step takes `O(R)`. The nested loops to check all `O(n²)` pairs take `O(n²)` time, as each check is `O(1)`. · **Space:** O(n²), primarily for the `n x n` adjacency matrix `isConnected`. The `degrees` array takes `O(n)` space. An alternative using an adjacency list of sets would be `O(n + R)`.
**Pros:** Efficient and well-suited for the given constraints.; The logic is straightforward and builds upon the brute-force idea with a standard optimization technique.
**Cons:** Requires extra space to store the graph structure and degrees, specifically `O(n^2)` for the adjacency matrix.
### Explanation
The bottleneck in the naive approach is re-calculating degrees and connections for every pair of cities. We can avoid this by processing the `roads` list just once to build data structures that give us the required information in O(1) time.

We can use:
1. An array `degrees` of size `n` to store the number of roads connected to each city.
2. A 2D boolean array `isConnected` of size `n x n` to act as an adjacency matrix. `isConnected[i][j]` will be `true` if there is a road between city `i` and city `j`, and `false` otherwise.

After populating these structures, we can proceed with the same nested loops to check all pairs `(i, j)`. However, the calculation inside the loop becomes an `O(1)` operation: `degrees[i] + degrees[j] - (isConnected[i][j] ? 1 : 0)`.

```java
class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        // Step 1: Pre-computation
        int[] degrees = new int[n];
        boolean[][] isConnected = new boolean[n][n];

        for (int[] road : roads) {
            int u = road[0];
            int v = road[1];
            degrees[u]++;
            degrees[v]++;
            isConnected[u][v] = true;
            isConnected[v][u] = true;
        }

        // Step 2: Iterate through all pairs and calculate rank
        int maxRank = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Rank is the sum of degrees, minus 1 if they are connected
                int currentRank = degrees[i] + degrees[j];
                if (isConnected[i][j]) {
                    currentRank--;
                }
                maxRank = Math.max(maxRank, currentRank);
            }
        }
        
        return maxRank;
    }
}
```
### Algorithm
- Initialize an integer array `degrees` of size `n` to store the degree of each city.
- Initialize a 2D boolean array `isConnected` of size `n x n` to store direct connections.
- Iterate through the `roads` array once to populate `degrees` and `isConnected`.
  - For each road `[u, v]`, increment `degrees[u]` and `degrees[v]`, and set `isConnected[u][v]` and `isConnected[v][u]` to `true`.
- Initialize `maxRank` to 0.
- Iterate through all unique pairs of cities `(i, j)` using a nested loop.
- For each pair, calculate the rank in `O(1)` time:
  - `currentRank = degrees[i] + degrees[j]`.
  - If `isConnected[i][j]` is `true`, subtract 1 from `currentRank`.
- Update `maxRank = max(maxRank, currentRank)`.
- Return `maxRank`.

# Solutions
### Java

```java
class Solution { public int maximalNetworkRank ( int n , int [][] roads ) { int [][] g = new int [ n ][ n ]; int [] cnt = new int [ n ]; for ( var r : roads ) { int a = r [ 0 ], b = r [ 1 ]; g [ a ][ b ] = 1 ; g [ b ][ a ] = 1 ; ++ cnt [ a ]; ++ cnt [ b ]; } int ans = 0 ; for ( int a = 0 ; a < n ; ++ a ) { for ( int b = a + 1 ; b < n ; ++ b ) { ans = Math . max ( ans , cnt [ a ] + cnt [ b ] - g [ a ][ b ]); } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int maximalNetworkRank ( int n , vector < vector < int >>& roads ) { int cnt [ n ]; int g [ n ][ n ]; memset ( cnt , 0 , sizeof ( cnt )); memset ( g , 0 , sizeof ( g )); for ( auto & r : roads ) { int a = r [ 0 ], b = r [ 1 ]; g [ a ][ b ] = g [ b ][ a ] = 1 ; ++ cnt [ a ]; ++ cnt [ b ]; } int ans = 0 ; for ( int a = 0 ; a < n ; ++ a ) { for ( int b = a + 1 ; b < n ; ++ b ) { ans = max ( ans , cnt [ a ] + cnt [ b ] - g [ a ][ b ]); } } return ans ; } };
```

### Python

```python
class Solution : def maximalNetworkRank ( self , n : int , roads : List [ List [ int ]]) -> int : g = defaultdict ( set ) for a , b in roads : g [ a ]. add ( b ) g [ b ]. add ( a ) ans = 0 for a in range ( n ): for b in range ( a + 1 , n ): if ( t : = len ( g [ a ]) + len ( g [ b ]) - ( a in g [ b ])) > ans : ans = t return ans
```