Maximal Network Rank

Med

#1484Time: 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.2 companies

Data structures

Graph

Companies

smartnews DRW

Prompt

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [a_i, b_i] indicates that there is a bidirectional road between cities a_i and b_i.

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 <= a_i, b_i <= n-1
a_i != b_i
Each pair of cities has at most one road connecting them.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

The number of roads connected to city i (its degree).
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.

1class Solution {2    public int maximalNetworkRank(int n, int[][] roads) {3        int maxRank = 0;4        // Iterate through all unique pairs of cities (i, j)5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                int degree_i = 0;8                int degree_j = 0;9                10                // Calculate degrees for i and j for the current pair11                for (int[] road : roads) {12                    if (road[0] == i || road[1] == i) {13                        degree_i++;14                    }15                    if (road[0] == j || road[1] == j) {16                        degree_j++;17                    }18                }19                20                // Check if the two cities are directly connected21                boolean connected = false;22                for (int[] road : roads) {23                    if ((road[0] == i && road[1] == j) || (road[0] == j && road[1] == i)) {24                        connected = true;25                        break;26                    }27                }28                29                int currentRank = degree_i + degree_j;30                if (connected) {31                    currentRank--;32                }33                34                maxRank = Math.max(maxRank, currentRank);35            }36        }37        return maxRank;38    }39}

Note: The two inner loops over roads can be combined into one for a slight optimization, but the overall complexity remains the same.

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

An array degrees of size n to store the number of roads connected to each city.
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).

1class Solution {2    public int maximalNetworkRank(int n, int[][] roads) {3        // Step 1: Pre-computation4        int[] degrees = new int[n];5        boolean[][] isConnected = new boolean[n][n];6 7        for (int[] road : roads) {8            int u = road[0];9            int v = road[1];10            degrees[u]++;11            degrees[v]++;12            isConnected[u][v] = true;13            isConnected[v][u] = true;14        }15 16        // Step 2: Iterate through all pairs and calculate rank17        int maxRank = 0;18        for (int i = 0; i < n; i++) {19            for (int j = i + 1; j < n; j++) {20                // Rank is the sum of degrees, minus 1 if they are connected21                int currentRank = degrees[i] + degrees[j];22                if (isConnected[i][j]) {23                    currentRank--;24                }25                maxRank = Math.max(maxRank, currentRank);26            }27        }28        29        return maxRank;30    }31}

Complexity

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)`.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem