Maximal Network Rank - Leetcode Solution

The Maximal Network Rank problem on LeetCode asks us to find the maximal network rank of a given city network. The network is represented by an n x n matrix called roads, where roads[i][j] = 1 denotes a direct connection between cities i and j, and roads[i][j] = 0 denotes no direct connection between the cities. The network rank of two different cities i and j is defined as the total number of direct connections to either city.

Our task is to find the maximum network rank of any two different cities in the network. Let’s take an example and walk through the solution strategy.

Example: n = 5 roads = [[0,1,1,0,0], [1,0,1,1,0], [1,1,0,1,1], [0,1,1,0,1], [0,0,1,1,0]]

The above network represents the city network with five cities (0, 1, 2, 3, 4). For instance, there is a direct connection between city 0 and city 1, a direct connection between city 1 and city 2, and so on.

Solution Strategy: We can start by iterating through the matrix and counting the number of connections for each city. Then, we can iterate again over the matrix and count the number of direct connections between any two different cities. Finally, we can find the two cities with the maximum network rank and return their total network rank.

Here's the Python code for the solution:

def maximalNetworkRank(n: int, roads: List[List[int]]) -> int:
    connections = [0] * n     
    
    for i in range(n):
        for j in range(n):
            if roads[i][j] == 1:
                connections[i] += 1
                connections[j] += 1
    
    networkRank = 0
    
    for i in range(n):
        for j in range(i + 1, n):
            # count direct connections between city i and city j
            rank = connections[i] + connections[j] - roads[i][j]
            networkRank = max(networkRank, rank)
            
    return networkRank

In the first loop, we calculate the number of connections for each city. We start by initializing the connections list with zeros and then iterate over the matrix. For every direct connection between cities i and j, we add 1 to the number of connections of both cities i and j.

In the second loop, we count the total direct connections between any two different cities. We start by iterating over the cities and their connections. Then, we add the number of connections of cities i and j and subtract the direct connection between cities i and j. Finally, we update the maximum network rank if the current rank is higher.

In the end, we return the maximum network rank found by the algorithm.

1