Leetcode 1615: Maximal Network Rank

Input: The input consists of an integer n representing the number of cities and an array roads, where each element in roads[i] = [ai, bi] represents a bidirectional road between cities ai and bi.

Example: n = 4, roads = [[0, 1], [0, 3], [1, 2], [1, 3]]

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.

Output: Return the maximal network rank, which is the highest network rank among all pairs of different cities.

Example: For n = 4 and roads = [[0, 1], [0, 3], [1, 2], [1, 3]], the output would be 4.

Constraints:

• The output should be a single integer representing the maximal network rank.

Goal: To find the maximal network rank, iterate through all pairs of cities and calculate their network rank by considering the number of directly connected roads to either city, ensuring duplicate counting is avoided.

Steps:

• First, calculate the number of roads connected to each city.

• Use a map to store connections between cities to avoid double counting the same road.

• For each pair of cities, calculate their combined network rank and update the maximum rank found.

• Return the highest network rank after checking all pairs of cities.

Goal: The problem has constraints on the number of cities and the number of roads, ensuring that the solution should efficiently handle the input size.

Steps:

• The number of cities n is between 2 and 100.

• The number of roads is at most n * (n - 1) / 2, meaning there can be at most a complete graph of roads.

Assumptions:

• The cities are numbered from 0 to n-1, and roads are bidirectional.

• Each pair of cities can have at most one direct road between them.

• Input: Input: n = 4, roads = [[0, 1], [0, 3], [1, 2], [1, 3]]

• Explanation: Here, cities 0 and 1 have 4 roads connected (0-1, 0-3, 1-2, 1-3). The maximal network rank is 4.

• Input: Input: n = 5, roads = [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]

• Explanation: For cities 1 and 2, the network rank is 5, as they are connected by 5 roads in total.

Approach: We can solve this problem by calculating the network rank for every pair of cities and selecting the maximum value.

Observations:

• We need to iterate through each pair of cities and calculate their network rank.

• The network rank for any pair of cities can be computed by summing the direct connections and subtracting any common connections.

Steps:

• Create an array to track the number of connections for each city.

• Use a map or set to store connections between cities to avoid counting any common road twice.

• Loop through all pairs of cities and calculate the network rank for each pair.

• Keep track of the highest network rank found during the iteration.

Empty Inputs:

• If there are no roads, the network rank is 0, as no cities are connected.

Large Inputs:

• For a large number of cities, the solution must be efficient to handle the upper limit of n = 100.

Special Values:

• If there are only two cities with one road, the network rank is simply 2.

Constraints:

• The algorithm must handle cases where the number of roads is minimal or maximal.

int maximalNetworkRank(int n, vector<vector<int>>& roads) {
    
    vector<int> inward(n, 0);
    map<int, set<int>> mp;
    for(auto it: roads) {
        inward[it[0]]++;
        inward[it[1]]++;
        mp[it[0]].insert(it[1]);
        mp[it[1]].insert(it[0]);
    }
    
    int mx = 0;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j) continue;
            mx = max(mx, inward[i] + inward[j] - (mp.count(i) && mp[i].count(j)? 1: 0));
        }
    }
    return mx;
}

1 : Function Definition

int maximalNetworkRank(int n, vector<vector<int>>& roads) {

Define the function `maximalNetworkRank` that takes the number of cities `n` and a list of roads as input.

2 : Variable Initialization

Prepare for variable initialization.

3 : Variable Initialization

    vector<int> inward(n, 0);

Initialize a vector `inward` of size `n` with all values set to 0 to keep track of the number of roads connected to each city.

4 : Data Structure Initialization

    map<int, set<int>> mp;

Initialize a map `mp` to store the cities and their respective connected cities using sets.

5 : Loop

    for(auto it: roads) {

Iterate through each road in the `roads` list.

6 : Inward Counting

        inward[it[0]]++;

Increase the count for the first city in the current road.

7 : Inward Counting

        inward[it[1]]++;

Increase the count for the second city in the current road.

8 : Graph Construction

        mp[it[0]].insert(it[1]);

Add the second city to the set of connected cities for the first city.

9 : Graph Construction

        mp[it[1]].insert(it[0]);

Add the first city to the set of connected cities for the second city.

10 : Max Calculation

    int mx = 0;

Initialize the variable `mx` to store the maximum network rank.

11 : Loop

    for(int i = 0; i < n; i++) {

Start a loop through each city in the graph.

12 : Loop

        for(int j = 0; j < n; j++) {

Start a nested loop to compare every pair of cities.

13 : Condition

            if(i == j) continue;

Skip if the two cities are the same.

14 : Max Calculation

            mx = max(mx, inward[i] + inward[j] - (mp.count(i) && mp[i].count(j)? 1: 0));

Calculate the network rank for the current pair of cities and update `mx` if a higher value is found.

15 : Return

    return mx;

Return the maximum network rank found.

Best Case: O(n^2)

Average Case: O(n^2)

Worst Case: O(n^2)

Description: In the worst case, we calculate the network rank for all pairs of cities, which results in O(n^2) time complexity.

Best Case: O(n)

Worst Case: O(n^2)

Description: The space complexity is O(n^2) due to storing the connections between cities, and O(n) in the best case if the roads are sparse.

Leetcode 1615: Maximal Network Rank

Explore →