1615. Maximal Network Rank


Problem Description

The problem defines an infrastructure consisting of n cities and some roads connecting these cities in a bidirectional manner. Given this setup, the concept of "network rank" for a pair of different cities is introduced. The network rank for any two different cities is the total number of roads that are connected to either of the two cities. However, if a road connects both cities directly, it is only counted once for their joint network rank.

Your task is to calculate the "maximal network rank" for the entire infrastructure. This is defined as the maximum network rank that can be achieved between any pair of different cities within the network. To find this, you are provided with two inputs: an integer n, representing the number of cities, and an array roads, where each element is a pair of integers representing a road between two cities.

The goal is to return the maximal network rank, which represents the highest connectivity between any two cities in the infrastructure, disregarding if any road is counted more than once across different pairs.

Intuition

To figure out the solution to this problem, we start by considering the straightforward approach for calculating the network rank of all possible pairs of different cities. We can do that by creating a graph representation where each node corresponds to a city, and the edges represent the roads between them.

The intuitive way to represent the graph is using a data structure where for each city, we maintain a set of the cities that are directly connected to it by a road. This can be done using a dictionary of sets in Python, represented as g in the provided solution.

Once we have the graph, we can iterate through all pairs of cities. For each pair, we calculate the sum of the roads connected to city A and the roads connected to city B. If there is a direct road between city A and B, we should decrease this sum by one because that road is counted twice - once for each city.

By iterating over each possible pair of different cities, we can keep track of the maximal network rank found. The intuition behind this approach is that we want to consider all the unique contributions of roads for every possible pair and find the pair with the highest connectivity.

The value is then stored in the variable ans, which gets updated every time we find a pair with a higher network rank. After considering all pairs, ans will hold the maximal network rank value, which is what we will return.

Solution Approach

The solution approach is based on a graph representation and iteration over all possible city pairs to find the maximal network rank. Here are the steps and key components of the algorithm:

  1. Graph Representation: The graph is stored in a dictionary called g. Each key in this dictionary represents a city, and the corresponding value is a set of all cities that have direct roads connected to this city. The use of a set here is to ensure unique entries and to easily check for the presence of a direct road between any two cities.

    1g = defaultdict(set)
    2for a, b in roads:
    3    g[a].add(b)
    4    g[b].add(a)
  2. Initialize Maximal Network Rank: A variable ans is initialized to 0 to keep track of the maximal network rank encountered during iteration.

    1ans = 0
  3. Iterating Over City Pairs: Two nested loops are used to iterate over all possible pairs of different cities. This is done by iterating through all cities as a in the outer loop and all cities after a as b in the inner loop to ensure that each pair is only considered once.

    1for a in range(n):
    2    for b in range(a + 1, n):
  4. Calculating the Network Rank: For each pair of cities (a, b), the network rank is computed as the sum of the number of cities connected to a and the number of cities connected to b. If city b is directly connected to city a, one is subtracted from the sum since that road is counted in both sets of connections.

    1if (t := len(g[a]) + len(g[b]) - (a in g[b])) > ans:
    2    ans = t

Using Python's walrus operator :=, we can calculate and compare the network rank in one line. The network rank for the pair is stored temporarily in the variable t, and if this is greater than the current ans, it means a new maximal network rank has been found, so ans is updated accordingly.

  1. Return the Result: After all pairs have been considered, the highest value of ans reflects the maximal network rank for the infrastructure.

    1return ans

This solution ensures that all city pairs are considered and the maximal network rank is found in an efficient manner. The time complexity of this solution is O(n^2) due to the nested loops over the city pairs, which is reasonable considering the pairwise nature of the network rank calculation.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described previously. Consider an infrastructure with n = 4 cities and the following array of roads connecting them:

1roads = [[0, 1], [0, 3], [1, 2], [1, 3]]

In this case, we have 4 cities and 4 roads. City 0 is connected to cities 1 and 3, city 1 is connected to cities 0, 2, and 3, city 2 is connected to city 1, and city 3 is connected to cities 0 and 1.

Step 1: Graph Representation

We represent our graph as a dictionary where each key is a city, and the corresponding value is a set of cities that it is directly connected to.

1g = defaultdict(set)
2g[0] = {1, 3}
3g[1] = {0, 2, 3}
4g[2] = {1}
5g[3] = {0, 1}

Step 2: Initialize Maximal Network Rank

We initialize our ans variable to zero.

1ans = 0

Step 3: Iterating Over City Pairs

We then loop over all pairs of different cities (a, b). Taking n = 4, we would loop over pairs(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3).

Step 4: Calculating the Network Rank

As we iterate over the pairs, we calculate the network rank for each pair:

  • For (0, 1): len(g[0]) + len(g[1]) - (0 in g[1]) = 2 + 3 - 1 = 4.
  • For (0, 2): len(g[0]) + len(g[2]) - (0 in g[2]) = 2 + 1 - 0 = 3.
  • For (0, 3): len(g[0]) + len(g[3]) - (0 in g[3]) = 2 + 2 - 1 = 3.
  • For (1, 2): len(g[1]) + len(g[2]) - (1 in g[2]) = 3 + 1 - 1 = 3.
  • For (1, 3): len(g[1]) + len(g[3]) - (1 in g[3]) = 3 + 2 - 1 = 4.
  • For (2, 3): len(g[2]) + len(g[3]) - (2 in g[3]) = 1 + 2 - 0 = 3.

We find that the maximal network rank for the pairs (0, 1) and (1, 3) is 4.

Step 5: Return the Result

After considering all pairs, we conclude that the maximal network rank is 4, as this is the highest network rank found from the pairwise considerations.

The returned result from our approach would be:

1return ans # which is 4 in this case

Python Solution

1from collections import defaultdict
2from typing import List
3
4class Solution:
5    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
6        # Create a graph using a dictionary, where each node points to a set of connected nodes
7        graph = defaultdict(set)
8      
9        # Build the graph with the given list of roads
10        for a, b in roads:
11            graph[a].add(b)
12            graph[b].add(a)
13      
14        # Initialize the maximum network rank to zero
15        max_network_rank = 0
16      
17        # Check every pair of cities to find the maximal network rank
18        for city_a in range(n):
19            for city_b in range(city_a + 1, n):
20                # Calculate the network rank for the pair (a, b), which is the sum of
21                # their connected cities minus one if they are directly connected
22                connected_cities = len(graph[city_a]) + len(graph[city_b])
23                if city_a in graph[city_b]:
24                    connected_cities -= 1
25              
26                # Update the maximum network rank if this pair has a higher rank
27                if connected_cities > max_network_rank:
28                    max_network_rank = connected_cities
29      
30        # Return the maximum network rank
31        return max_network_rank
32

Java Solution

1class Solution {
2    public int maximalNetworkRank(int n, int[][] roads) {
3        int[][] graph = new int[n][n];
4        int[] count = new int[n];
5        // Fill the graph matrix and count array
6        for (int[] road : roads) {
7            int cityA = road[0];
8            int cityB = road[1];
9            graph[cityA][cityB] = 1; // Mark the road as existing between cityA and cityB
10            graph[cityB][cityA] = 1; // Mark the road as existing between cityB and cityA
11            // Increment the count of roads connected to cityA and cityB
12            ++count[cityA];
13            ++count[cityB];
14        }
15      
16        int maxNetworkRank = 0;
17        // Iterate through all pairs of cities to find
18        // the maximal network rank of the transportation network
19        for (int cityA = 0; cityA < n; ++cityA) {
20            for (int cityB = cityA + 1; cityB < n; ++cityB) {
21                // Calculate network rank as the sum of roads for both cities minus
22                // the road between them if it exists
23                int networkRank = count[cityA] + count[cityB] - graph[cityA][cityB];
24                // Update the maximum network rank if the current rank is higher
25                maxNetworkRank = Math.max(maxNetworkRank, networkRank);
26            }
27        }
28        // Return the maximum network rank found
29        return maxNetworkRank;
30    }
31}
32

C++ Solution

1#include <vector> // Include vector header for using std::vector
2#include <cstring> // Include cstring header for using memset
3#include <algorithm> // Include algorithm header for using std::max
4
5class Solution {
6public:
7    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
8        // Initialize count and graph matrices using vectors for dynamic size allocation
9        vector<int> count(n, 0);
10        vector<vector<int>> graph(n, vector<int>(n, 0)); 
11
12        // Iterate over the roads to populate the graph and counts of connected roads for each city
13        for (auto& road : roads) {
14            int cityA = road[0], cityB = road[1];
15            graph[cityA][cityB] = graph[cityB][cityA] = 1; // Mark the cities as connected
16            ++count[cityA]; // Increment road count for cityA
17            ++count[cityB]; // Increment road count for cityB
18        }
19
20        int maxRank = 0; // Initialize the max network rank
21
22        // Iterate over pairs of cities to calculate the network rank
23        for (int cityA = 0; cityA < n; ++cityA) {
24            for (int cityB = cityA + 1; cityB < n; ++cityB) {
25                // Calculate rank for the pair (cityA, cityB) and update the maxRank if it's higher
26                maxRank = std::max(maxRank, count[cityA] + count[cityB] - graph[cityA][cityB]);
27            }
28        }
29
30        return maxRank; // Return the maximum network rank found
31    }
32};
33

Typescript Solution

1function maximalNetworkRank(n: number, roads: number[][]): number {
2    // Create an adjacency matrix for the graph
3    const graph: number[][] = Array.from(new Array(n), () => new Array(n).fill(0));
4    // Initialize a counter array to keep track of the number of roads each city has
5    const roadCount: number[] = new Array(n).fill(0);
6
7    // Build the graph by incrementing the road count for each city and 
8    // marking the cities as connected in the adjacency matrix
9    for (const [cityA, cityB] of roads) {
10        graph[cityA][cityB] = 1;
11        graph[cityB][cityA] = 1;
12        ++roadCount[cityA];
13        ++roadCount[cityB];
14    }
15
16    // Initialize maximum network rank to 0
17    let maxRank = 0;
18
19    // Iterate over each pair of cities and calculate the network rank
20    for (let cityA = 0; cityA < n; ++cityA) {
21        for (let cityB = cityA + 1; cityB < n; ++cityB) {
22            // Network rank is the sum of roads for both cities, subtracting 1 if they have a direct road
23            maxRank = Math.max(maxRank, roadCount[cityA] + roadCount[cityB] - graph[cityA][cityB]);
24        }
25    }
26
27    // Return the maximum network rank found
28    return maxRank;
29}
30

Time and Space Complexity

The given code snippet calculates the maximal network rank, which is defined as the maximum number of directly connected roads to any two different cities.

Time Complexity

The time complexity of the code can be broken down into two parts:

  1. Building the graph: The first for loop goes through all the roads, which is given by the size of the input roads. If the number of roads is m, then this part of the code has a complexity of O(m) where m is the number of edges (roads) in the graph.

  2. Calculating the maximal network rank: The nested for loop considers each pair of distinct cities exactly once. Since there are n cities, and the loop for the second city starts at one more than the current first city, this results in a total of n * (n - 1) / 2 iterations. Within each iteration, the code performs a constant amount of work; hence, the time complexity of this part is O(n^2).

Therefore, the total time complexity is the sum of both parts, which can be expressed as O(m + n^2).

Space Complexity

The space complexity of the code can be analyzed as follows:

  1. Graph storage: A defaultdict(set) data structure is used to store the graph, which will contain at most m edges. Since each edge is stored twice (once for each node it connects), the space required for the graph storage is O(2m), which simplifies to O(m).

  2. Additional variables: The code uses a constant amount of additional space for variables such as ans, a, b, and t.

Therefore, the space complexity of the entire code is O(m) considering the graph's representation is the dominant factor.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫