{x}
blog image

Maximal Network Rank

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.

Solution Explanation for Maximal Network Rank

This problem involves finding the maximal network rank among all pairs of different cities in an infrastructure. The network rank between two cities is the total number of roads directly connected to either city, with roads connected to both cities counted only once.

Approach:

The most efficient approach uses a combination of adjacency matrix and degree counting.

  1. Degree Counting: We first create a degree array cnt to store the degree (number of connected roads) for each city. This is done by iterating through the roads array and incrementing the degree count for each city involved in each road.

  2. Adjacency Matrix (Optional but Helpful): While not strictly necessary, an adjacency matrix g simplifies calculating the network rank. g[i][j] is 1 if there's a road between city i and j, and 0 otherwise. This allows quick checking if a road is shared between two cities.

  3. Iterating and Calculating Network Rank: We iterate through all possible pairs of distinct cities (nested loops). For each pair (a, b), the network rank is calculated as: cnt[a] + cnt[b] - g[a][b]. Subtracting g[a][b] corrects for double-counting shared roads. The maximum network rank encountered is stored and returned.

Time Complexity Analysis:

  • Degree counting: O(E), where E is the number of roads.
  • Creating the adjacency matrix (if used): O(n^2), where n is the number of cities.
  • Iterating through city pairs and calculating network rank: O(n^2).

Therefore, the overall time complexity is dominated by the nested loops, resulting in O(n^2). In the worst case (a fully connected graph), E is O(n^2), so the degree counting step doesn't change the overall complexity.

Space Complexity Analysis:

  • cnt array: O(n)
  • g matrix (if used): O(n^2)

Thus, the overall space complexity is O(n^2) if the adjacency matrix is used; otherwise, it's O(n).

Code Implementation (Python):

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        g = [[0] * n for _ in range(n)]  # Adjacency matrix (optional)
        cnt = [0] * n  # Degree array
 
        for a, b in roads:
            g[a][b] = g[b][a] = 1
            cnt[a] += 1
            cnt[b] += 1
 
        max_rank = 0
        for a in range(n):
            for b in range(a + 1, n):  # Avoid duplicate pairs and self-loops
                max_rank = max(max_rank, cnt[a] + cnt[b] - g[a][b])
 
        return max_rank

Code Implementation (Other Languages): The core logic remains the same across languages; the syntax will vary. See the provided code in Java, C++, Go, and TypeScript for examples. The structure will follow the same three-step process outlined above.