LeetCode 1615 - Maximal Network Rank

The problem asks us to compute the maximal network rank for a set of cities connected by bidirectional roads. Each city can be thought of as a node in a graph, and each road as an undirected edge.

leetcodemediumgraph-theory

LeetCode Problem 1615

Difficulty: 🟡 Medium
Topics: Graph Theory

Solution

Problem Understanding

The problem asks us to compute the maximal network rank for a set of cities connected by bidirectional roads. Each city can be thought of as a node in a graph, and each road as an undirected edge. The network rank of a pair of cities is the total number of roads connected to either city, with a shared road counted only once. The goal is to examine all possible pairs of cities and determine which pair achieves the maximum combined connectivity.

The input consists of an integer n representing the number of cities labeled from 0 to n-1, and a list roads where each element [a, b] represents a direct connection between cities a and b. The output is a single integer representing the maximal network rank.

Constraints tell us that n is at most 100 and there can be up to n*(n-1)/2 roads, meaning a fully connected graph is possible. The input guarantees that there are no duplicate roads and no self-loops, which simplifies handling edge counting.

Edge cases to consider include cities with no roads, fully connected cities, and pairs where the two cities share a direct road versus pairs that do not.

Approaches

A brute-force approach involves calculating the network rank for every pair of cities. We could iterate over all pairs (i, j) and count the roads directly connected to i and j, making sure to subtract one if they share a direct road. While this is correct, it involves checking every road for every pair, giving a time complexity of O(n^2 * m) where m is the number of roads. This is feasible for small n but inefficient when n approaches 100.

The optimal approach leverages two observations. First, we only need the degree of each city (the number of roads connected to it). Second, we need to know which cities are directly connected to handle the "subtract one if shared" rule. Using an adjacency matrix (or a set per city) allows us to compute the maximal network rank by iterating through all pairs and computing degree[i] + degree[j] - (1 if i and j are connected else 0). This reduces the complexity to O(n^2) for the pairwise calculation and O(m) for preprocessing, which is efficient for the given constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2 * m) O(1) Check every pair of cities and count connections by scanning the roads list
Optimal O(n^2 + m) O(n^2 or n*m) Precompute degrees and adjacency info, then iterate all pairs

Algorithm Walkthrough

  1. Initialize an array degree of size n to track the number of roads connected to each city.
  2. Initialize an n x n adjacency matrix connected or a list of sets to track if two cities are directly connected.
  3. Iterate through each road [a, b] in roads. Increment degree[a] and degree[b]. Mark connected[a][b] and connected[b][a] as True.
  4. Initialize max_rank to 0.
  5. Iterate through all pairs of cities (i, j) where i < j. Compute rank = degree[i] + degree[j] - (1 if connected[i][j] else 0). Update max_rank if rank is higher.
  6. Return max_rank.

Why it works: The algorithm guarantees correctness because it computes the exact degree for each city, accounts for shared roads exactly once, and evaluates every pair of cities. By iterating through all pairs, it ensures that no possible maximal network rank is missed.

Python Solution

from typing import List

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        degree = [0] * n
        connected = [[False] * n for _ in range(n)]
        
        for a, b in roads:
            degree[a] += 1
            degree[b] += 1
            connected[a][b] = True
            connected[b][a] = True
        
        max_rank = 0
        for i in range(n):
            for j in range(i + 1, n):
                rank = degree[i] + degree[j] - (1 if connected[i][j] else 0)
                max_rank = max(max_rank, rank)
        
        return max_rank

The Python implementation uses a list to store each city's degree and a 2D list to mark connections. By iterating through each road once, the degrees and connections are computed efficiently. Then, iterating over all pairs ensures we find the maximum network rank.

Go Solution

func maximalNetworkRank(n int, roads [][]int) int {
    degree := make([]int, n)
    connected := make([][]bool, n)
    for i := 0; i < n; i++ {
        connected[i] = make([]bool, n)
    }

    for _, road := range roads {
        a, b := road[0], road[1]
        degree[a]++
        degree[b]++
        connected[a][b] = true
        connected[b][a] = true
    }

    maxRank := 0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            rank := degree[i] + degree[j]
            if connected[i][j] {
                rank--
            }
            if rank > maxRank {
                maxRank = rank
            }
        }
    }
    
    return maxRank
}

The Go implementation mirrors Python but uses slices for the adjacency matrix and handles indexing explicitly. Go does not require type hints for slices, and boolean slices are initialized explicitly for each row.

Worked Examples

Example 1:

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

City Degree Connections
0 2 1, 3
1 3 0, 2, 3
2 1 1
3 2 0, 1

Pairs evaluation:

  • (0,1): 2 + 3 - 1 = 4
  • (0,2): 2 + 1 - 0 = 3
  • (0,3): 2 + 2 - 1 = 3
  • (1,2): 3 + 1 - 1 = 3
  • (1,3): 3 + 2 - 1 = 4
  • (2,3): 1 + 2 - 0 = 3

Maximal network rank = 4

Example 2 and 3 follow similarly.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2 + m) Computing degrees and adjacency takes O(m), iterating over all city pairs takes O(n^2)
Space O(n^2) Adjacency matrix requires O(n^2) space, degrees array O(n)

The algorithm scales well up to n = 100, since n^2 = 10,000 is reasonable.

Test Cases

# Provided examples
assert Solution().maximalNetworkRank(4, [[0,1],[0,3],[1,2],[1,3]]) == 4  # example 1
assert Solution().maximalNetworkRank(5, [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]) == 5  # example 2
assert Solution().maximalNetworkRank(8, [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]) == 5  # example 3

# Edge cases
assert Solution().maximalNetworkRank(2, []) == 0  # no roads
assert Solution().maximalNetworkRank(2, [[0,1]]) == 1  # single road
assert Solution().maximalNetworkRank(3, [[0,1],[1,2],[0,2]]) == 2  # fully connected small graph
assert Solution().maximalNetworkRank(4, [[0,1],[1,2],[2,3]]) == 3  # linear graph
Test Why
No roads Handles zero connectivity
Single road Minimum graph connectivity
Fully connected small graph Ensures shared edge is counted once
Linear graph Tests pairs without direct connection

Edge Cases

The first edge case is a graph with no roads, where the maximal network rank should be 0 because no city has any connection. The algorithm handles this naturally since all degrees are zero.

The second edge case is a graph with all cities connected to each other, a fully connected graph. Here, the maximal network rank equals 2*(n-1) - 1 because any pair shares a road. The adjacency matrix ensures we subtract 1 for shared edges, giving the correct result.

The third edge case is a graph with some cities isolated, meaning some cities have no connections at all. When pairing such a city with