#1615

Medium

auto_awesomeGraph-driven solution strategy

LeetCode Problem Workspace

Maximal Network Rank

Calculate the maximum network rank of two cities by analyzing all city pairs using a graph-driven solution strategy efficiently.

graph

Problem Statement

You are given an infrastructure of n cities numbered from 0 to n-1 with a list of bidirectional roads connecting them. Each road is represented as roads[i] = [ai, bi], indicating a direct road between city ai and city bi. No pair of cities has more than one direct road, and a city cannot have a road to itself.

The network rank of two distinct cities is defined as the sum of the number of roads directly connected to either city. If the two cities share a direct road, count it only once. Your task is to determine the maximal network rank, which is the highest network rank achievable among all pairs of different cities.

Examples

Example 1

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

Output: 4

The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Example 2

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

Output: 5

There are 5 roads that are connected to cities 1 or 2.

Example 3

Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]

Output: 5

The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.

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.

Solution Approach

Map Road Connections

Create an array to count the number of roads connected to each city. Additionally, maintain a set or matrix to record whether a direct road exists between any two cities. This structure enables fast computation of network rank for each city pair.

Iterate Through All Pairs

Use nested loops to consider every unique pair of different cities. For each pair, calculate their combined network rank by summing their road counts and subtracting one if they share a direct road. Update the maximal network rank whenever a higher value is found.

Return Maximal Network Rank

After evaluating all pairs, return the largest network rank computed. This ensures that the result correctly reflects the pair of cities with the most extensive combined road connections.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to evaluating all city pairs. Space complexity is O(n^2) if using a matrix for direct road tracking, or O(n + m) using adjacency lists and counts, where m is the number of roads.

What Interviewers Usually Probe

Focus on computing the network rank for each city pair correctly, especially handling shared roads.
Optimize storage and access of road connections for fast lookup to avoid repeated scanning.
Consider the trade-off between using an adjacency matrix versus adjacency list for space and speed.

Common Pitfalls or Variants

Common pitfalls

Double-counting a road that connects both cities when calculating network rank.
Forgetting to iterate through all unique pairs, potentially missing the maximal rank.
Using inefficient structures leading to excessive time complexity on larger n values.

Follow-up variants

Compute the second highest network rank instead of the maximal one.
Allow multiple roads between the same pair of cities and adjust the counting logic.
Extend to weighted roads where the network rank sums road weights rather than counts.

FAQ

What is the definition of network rank in the Maximal Network Rank problem?

Network rank of two cities is the total number of roads connected to either city, counting a shared road only once.

Can cities with no connecting roads affect the maximal network rank?

Yes, cities with fewer connections reduce the network rank when paired, but the maximal rank is determined by the most connected pairs.

Is there a preferred data structure to track road connections efficiently?

An adjacency matrix or adjacency list works; the choice depends on balancing lookup speed and space usage for n cities.

How does GhostInterview help avoid common pitfalls in this problem?

It highlights shared road handling, ensures all city pairs are evaluated, and tracks counts systematically to prevent double-counting.

What strategy should I use for maximal network rank calculations?

Use a graph-driven approach: count connections per city, check all unique pairs, subtract shared roads, and track the maximum value.

terminal

Solution

Solution 1: Counting

We can use a one-dimensional array $\textit{cnt}$ to record the degree of each city and a two-dimensional array $\textit{g}$ to record whether there is a road between each pair of cities. If there is a road between city $a$ and city $b$, then $\textit{g}[a][b] = \textit{g}[b][a] = 1$; otherwise, $\textit{g}[a][b] = \textit{g}[b][a] = 0$.

1

2

3

4

5

6

7

8

9

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        g = [[0] * n for _ in range(n)]
        cnt = [0] * n
        for a, b in roads:
            g[a][b] = g[b][a] = 1
            cnt[a] += 1
            cnt[b] += 1
        return max(cnt[a] + cnt[b] - g[a][b] for a in range(n) for b in range(a + 1, n))

Continue Practicing

#1632 rank transform of a matrix #1591 strange printer ii #1584 min cost to connect all points