Code Implementation

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        from collections import defaultdict
        degree = [0] * n
        connected = set()
        for a, b in roads:
            degree[a] += 1
            degree[b] += 1
            connected.add((min(a, b), max(a, b)))
        max_rank = 0
        for i in range(n):
            for j in range(i+1, n):
                rank = degree[i] + degree[j]
                if (i, j) in connected:
                    rank -= 1
                max_rank = max(max_rank, rank)
        return max_rank
      

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        vector<int> degree(n, 0);
        set<pair<int, int>> connected;
        for (const auto& road : roads) {
            int a = road[0], b = road[1];
            degree[a]++;
            degree[b]++;
            connected.insert({min(a, b), max(a, b)});
        }
        int maxRank = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int rank = degree[i] + degree[j];
                if (connected.count({i, j})) rank--;
                maxRank = max(maxRank, rank);
            }
        }
        return maxRank;
    }
};
      

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        int[] degree = new int[n];
        boolean[][] connected = new boolean[n][n];
        for (int[] road : roads) {
            int a = road[0], b = road[1];
            degree[a]++;
            degree[b]++;
            connected[a][b] = true;
            connected[b][a] = true;
        }
        int maxRank = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int rank = degree[i] + degree[j];
                if (connected[i][j]) rank--;
                maxRank = Math.max(maxRank, rank);
            }
        }
        return maxRank;
    }
}
      

var maximalNetworkRank = function(n, roads) {
    const degree = new Array(n).fill(0);
    const connected = new Set();
    for (const [a, b] of roads) {
        degree[a]++;
        degree[b]++;
        connected.add(`${Math.min(a, b)}#${Math.max(a, b)}`);
    }
    let maxRank = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            let rank = degree[i] + degree[j];
            if (connected.has(`${i}#${j}`)) rank--;
            maxRank = Math.max(maxRank, rank);
        }
    }
    return maxRank;
};
      

Problem Description

Given n cities numbered from 0 to n-1 and a list of bidirectional roads (edges) represented by roads, where each road connects two different cities, you are to determine the maximal network rank of the network.

The network rank of a pair of different cities A and B is defined as the total number of roads connected to either A or B, counting a road that connects both A and B only once.

Your task is to return the largest network rank among all pairs of different cities.

• Each road connects two distinct cities.
• There are no duplicate roads.
• Constraints: 2 ≤ n ≤ 100, 0 ≤ roads.length ≤ n*(n-1)/2

Thought Process

The problem asks us to find the pair of cities with the highest combined number of directly connected roads, not double-counting the road if they are directly connected.

The brute-force approach would be to check every possible pair of cities, count their total connections, and subtract one if they are directly connected. However, with up to 100 cities, checking every pair is feasible (since there are at most 4950 pairs), but we should still aim for clarity and efficiency.

To optimize, we can precompute the number of roads connected to each city (their degree) and keep a set or matrix to quickly check if two cities are directly connected.

This approach is straightforward and avoids recalculating connections for every pair, making the solution efficient and easy to understand.

Solution Approach

• Step 1: Count Connections
  • For each city, count how many roads are directly connected to it. This is known as the city's degree.
• Step 2: Track Direct Connections
  • Use a set (or a 2D boolean array) to record which pairs of cities are directly connected by a road. This lets us quickly check if a pair shares a direct road.
• Step 3: Evaluate All Pairs
  • For every pair of different cities (i, j), calculate their network rank as degree[i] + degree[j].
  • If i and j are directly connected, subtract 1 (since we shouldn't double-count their shared road).
  • Track the maximum network rank found among all pairs.
• Step 4: Return the Result
  • After checking all pairs, return the highest network rank found.

We use arrays for degree counts (constant-time lookup) and sets or boolean arrays for direct connection checks (also constant-time). This keeps the solution efficient and simple.

Example Walkthrough

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

1. Count degrees:
   • City 0: connected to 1 and 3 → degree = 2
   • City 1: connected to 0, 2, 3 → degree = 3
   • City 2: connected to 1 → degree = 1
   • City 3: connected to 0, 1 → degree = 2
2. Direct connections:
   • (0,1), (0,3), (1,2), (1,3)
3. Check all pairs:
   • (0,1): 2+3=5, directly connected → rank=4
   • (0,2): 2+1=3, not directly connected → rank=3
   • (0,3): 2+2=4, directly connected → rank=3
   • (1,2): 3+1=4, directly connected → rank=3
   • (1,3): 3+2=5, directly connected → rank=4
   • (2,3): 1+2=3, not directly connected → rank=3
4. Maximum network rank is 4 (for pairs (0,1) and (1,3)).

Time and Space Complexity

• Brute-force Approach:
  • For every pair of cities, count all roads connected to either city, checking each road for both cities: O(n² * m), where m is the number of roads.
• Optimized Approach:
  • Counting degrees: O(m), where m is the number of roads.
  • Building direct connection set/matrix: O(m).
  • Checking all pairs: O(n²), since there are n(n-1)/2 pairs.
  • Total time: O(n² + m).
  • Space: O(n) for degrees + O(n²) for connection matrix, or O(m) for set of pairs.

Since n is at most 100, these time and space complexities are acceptable.

Summary

To solve the Maximal Network Rank problem, we first compute how many roads connect to each city and quickly check if two cities are directly connected. We then evaluate every pair, summing their degrees and subtracting one if they share a direct road. This approach is efficient, easy to implement, and leverages simple data structures for fast lookups. The key insight is to avoid redundant counting and to precompute relationships, making the solution both elegant and effective.