Maximal Network Rank

MEDIUM

Description

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

Checkout 2 different approaches to solve Maximal Network Rank. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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.

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as it only uses a few variables to store intermediate values and does not depend on the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Maximal Network Rank. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Maximal Network Rank

Data Structures:

Graph

Companies:

smartnews |DRW |