Leetcode # 1615. Maximal Network Rank

https://leetcode.com/problems/maximal-network-rank

Solution

E := number of edges = len(cities)
V := number of vertexes/nodes = len(roads)

Time Complexity: O(E + V ** 2)
Space Complexity: O(E)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
    roads_ = defaultdict(set)
    for a, b in roads:
      road = (min(a, b), max(a, b))
      roads_[a].add(road)
      roads_[b].add(road)
    cities = sorted(roads_.keys())
    max_network_rank = 0
    for i in range(len(cities)):
      for j in range(i + 1, len(cities)):
        max_network_rank = max(
          max_network_rank, 
          len(roads_[cities[i]] | roads_[cities[j]])
        )
    return max_network_rank

Last Updated on 2023/08/18 by A1go