### View *Maximal Network Rank* on LeetCode

## Statistics

**Time Spent Coding**

10 minutes

**Time Complexity**

O(n^{2}) - Each possible pair in the graph must be visited, resulting in the O(n^{2}) time complexity.

**Space Complexity**

O(n^{n}) - In the worst case, each node is connected, making each node stored n times, resulting in the O(n^{n}) space complexity.

**Runtime Beats**

68.91% of other submissions

## Explanation

*Comments explain the algorithm*

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
dic = {}
# Create a dictionary of empty sets for each possible node
for i in range(n):
dic[i] = set()
# Add each node to each other set
for c1, c2 in roads:
dic[c1].add(c2)
dic[c2].add(c1)
max_net = 0
# Double for loop allows for each pair of nodes to be checked
for i in range(n-1):
for j in range(i+1,n):
# The length of both sets is their maximum network
tot = len(dic[i]) + len(dic[j])
# If the pair is connected, then subtract one to account for the duplicate
if i in dic[j]: tot -= 1
# Update max_net if tot is greater than the current max_net
max_net = max(tot,max_net)
return max_net