Problem Description

You are given n cities numbered from 0 to n-1 and an array roads where each roads[i] = [ai, bi] represents a bidirectional road connecting city ai and city bi.

The network rank of two different cities is defined as the total number of roads that are directly connected to either of the two cities. If a road directly connects both cities, it is counted only once (not twice).

Your task is to find the maximal network rank of the infrastructure, which is the maximum network rank among all possible pairs of different cities.

For example, if city A has 3 roads connected to it and city B has 4 roads connected to it:

• If there is a direct road between A and B, their network rank would be 3 + 4 - 1 = 6 (subtract 1 because the road between them is counted in both cities' connections)
• If there is no direct road between A and B, their network rank would be 3 + 4 = 7

The goal is to examine all possible pairs of cities and return the highest network rank found.

Intuition

To find the maximal network rank, we need to understand what contributes to the network rank of any two cities. For any pair of cities, their network rank is the sum of roads connected to each city. However, if the two cities are directly connected to each other, we've counted that shared road twice (once for each city), so we need to subtract it once.

This leads us to a straightforward approach: we need to know two pieces of information:

1. How many roads are connected to each city (the degree of each city)
2. Whether any two cities are directly connected

With this information, for any pair of cities (a, b), we can calculate their network rank as:

• degree[a] + degree[b] - 1 if cities a and b are directly connected
• degree[a] + degree[b] if cities a and b are not directly connected

Since we want the maximal network rank, we need to check all possible pairs of cities. For n cities, there are n * (n-1) / 2 unique pairs to check.

The key insight is that we don't need any complex graph algorithms here - just simple counting and checking. We can preprocess the graph to store each city's connections in a set (for quick lookup of whether two cities are connected) and then systematically check every pair to find the maximum network rank.

This gives us the formula: network_rank = len(connections[a]) + len(connections[b]) - (1 if a in connections[b] else 0)

Learn more about Graph patterns.

Solution Approach

The implementation uses a graph representation to efficiently solve this problem. Let's walk through the key components:

Data Structure Setup: We use a defaultdict(set) to store the graph g, where each key represents a city and its value is a set containing all cities directly connected to it. Using a set allows O(1) lookup time to check if two cities are connected.

Building the Graph: For each road [a, b] in the input:

• Add city b to the set of connections for city a: g[a].add(b)
• Add city a to the set of connections for city b: g[b].add(a)

This creates a bidirectional representation of the road network.

Finding Maximum Network Rank: We enumerate all possible pairs of cities using nested loops:

• Outer loop: for a in range(n) - iterates through each city
• Inner loop: for b in range(a + 1, n) - ensures we only check each pair once (avoiding duplicates like (a,b) and (b,a))

For each pair (a, b), we calculate the network rank using the formula:

network_rank = len(g[a]) + len(g[b]) - (a in g[b])

Here's what each component means:

• len(g[a]): number of roads connected to city a
• len(g[b]): number of roads connected to city b
• (a in g[b]): returns True (1) if cities are directly connected, False (0) otherwise

The expression (a in g[b]) cleverly handles the subtraction: if the cities are connected, we subtract 1 to avoid double-counting their shared road; otherwise, we subtract 0.

Time Complexity: O(n²) for checking all pairs, where n is the number of cities Space Complexity: O(E) where E is the number of roads, for storing the graph

Example Walkthrough

Let's walk through a small example with 4 cities (numbered 0-3) and the following roads:

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

Step 1: Build the Graph

We create our adjacency list using a defaultdict(set):

• City 0 connects to: {1, 3}
• City 1 connects to: {0, 2, 3}
• City 2 connects to: {1}
• City 3 connects to: {0, 1}

Step 2: Calculate Network Rank for Each Pair

Now we check all possible pairs of cities:

Pair (0, 1):

• City 0 has 2 connections
• City 1 has 3 connections
• They are directly connected (0 is in city 1's set)
• Network rank = 2 + 3 - 1 = 4

Pair (0, 2):

• City 0 has 2 connections
• City 2 has 1 connection
• They are NOT directly connected
• Network rank = 2 + 1 - 0 = 3

Pair (0, 3):

• City 0 has 2 connections
• City 3 has 2 connections
• They are directly connected (0 is in city 3's set)
• Network rank = 2 + 2 - 1 = 3

Pair (1, 2):

• City 1 has 3 connections
• City 2 has 1 connection
• They are directly connected (1 is in city 2's set)
• Network rank = 3 + 1 - 1 = 3

Pair (1, 3):

• City 1 has 3 connections
• City 3 has 2 connections
• They are directly connected (1 is in city 3's set)
• Network rank = 3 + 2 - 1 = 4

Pair (2, 3):

• City 2 has 1 connection
• City 3 has 2 connections
• They are NOT directly connected
• Network rank = 1 + 2 - 0 = 3

Step 3: Find Maximum

The maximum network rank among all pairs is 4, which occurs for pairs (0,1) and (1,3).

The formula len(g[a]) + len(g[b]) - (a in g[b]) elegantly handles both cases:

• When cities are connected: the boolean expression evaluates to True (1), subtracting the shared road
• When cities aren't connected: the boolean expression evaluates to False (0), adding both cities' full connection counts

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 + m) where n is the number of cities and m is the number of roads.

• Building the graph takes O(m) time as we iterate through all roads once
• The nested loops iterate through all pairs of cities, which gives us O(n^2) iterations
• For each pair, we perform constant time operations: checking set membership (a in g[b]) and calculating the sum of degrees
• Therefore, the overall time complexity is O(m + n^2) = O(n^2) when simplified, since in the worst case m = O(n^2)

Space Complexity: O(n + m) which simplifies to O(n^2) in the worst case.

• The graph g is stored as a dictionary of sets
• In the worst case (complete graph), each city connects to all other cities
• This means we store up to n sets, and each set can contain up to n-1 cities
• Additionally, we store each edge twice (once for each direction in the adjacency sets)
• Therefore, the space complexity is O(n + 2m) = O(n + m), which becomes O(n^2) when m = O(n^2) in a dense graph

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Double-Counting City Pairs

A frequent mistake is using two complete nested loops for a in range(n): for b in range(n): without proper filtering. This leads to:

• Checking the same pair twice (e.g., (0,1) and (1,0))
• Comparing a city with itself (e.g., (0,0))

Incorrect approach:

for city_a in range(n):
    for city_b in range(n):  # Wrong: includes duplicates and self-pairs
        if city_a != city_b:  # Still processes (a,b) and (b,a)
            rank = len(graph[city_a]) + len(graph[city_b]) - (city_a in graph[city_b])

Correct approach:

for city_a in range(n):
    for city_b in range(city_a + 1, n):  # Ensures each pair is checked only once
        rank = len(graph[city_a]) + len(graph[city_b]) - (city_a in graph[city_b])

2. Using Lists Instead of Sets for Adjacency Storage

Storing connections as lists rather than sets creates performance issues:

• Checking if two cities are connected becomes O(degree) instead of O(1)
• Can accidentally add duplicate connections

Problematic implementation:

graph = defaultdict(list)  # Using list instead of set
for a, b in roads:
    graph[a].append(b)
    graph[b].append(a)

# Later checking connection is O(degree) operation
if city_b in graph[city_a]:  # Linear search through list
    current_rank -= 1

Optimal implementation:

graph = defaultdict(set)  # Using set for O(1) lookups
for a, b in roads:
    graph[a].add(b)
    graph[b].add(a)

3. Forgetting to Handle Isolated Cities

When using defaultdict, isolated cities (with no roads) are handled automatically. However, if using a regular dictionary, you might encounter KeyError:

Error-prone code:

graph = {}
for a, b in roads:
    if a not in graph:
        graph[a] = set()
    if b not in graph:
        graph[b] = set()
    graph[a].add(b)
    graph[b].add(a)

# This fails if a city has no roads
for city_a in range(n):
    for city_b in range(city_a + 1, n):
        rank = len(graph[city_a]) + len(graph[city_b])  # KeyError if city not in graph

Safe approach:

# Either use defaultdict or handle missing keys explicitly
rank = len(graph.get(city_a, set())) + len(graph.get(city_b, set()))

4. Incorrect Subtraction Logic for Connected Cities

A subtle but critical error is forgetting to check if cities are connected or incorrectly implementing the check:

Wrong implementations:

# Forgot to subtract shared road
rank = len(graph[city_a]) + len(graph[city_b])

# Always subtracting 1
rank = len(graph[city_a]) + len(graph[city_b]) - 1

# Checking wrong direction (though this works with bidirectional graph)
rank = len(graph[city_a]) + len(graph[city_b]) - (city_b in graph[city_a])

The boolean expression (city_a in graph[city_b]) elegantly converts to 1 or 0, making the subtraction automatic and correct.