< Back




1615. Maximal Network Rank

Network rank for this graph is being calculated by taking a pair of nodes and counting the number of
edges connected to them, less the edge connected between the two nodes. To solve this, we create an
array to track the number of edges connected to each node. We also maintain a graph to keep track of
whether or not a pair of nodes are connected.

We process each possible pair of nodes, adding their connected edges and subtracting the edge between
them - maximizing our answer across this process.

The solution is as follows:


  class Solution:
      def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
          conns = [0] * n
          graph = [[False] * n for _ in range(n)]

          for u, v in roads:
              conns[u] += 1
              conns[v] += 1
              graph[u][v] = graph[v][u] = True

          ans = 0
          for i in range(n):
              for j in range(i + 1, n):
                  rank = conns[i] + conns[j]

                  if graph[i][j]:
                      rank -= 1

                  ans = max(ans, rank)
          
          return ans


_ Time Complexity:

  O(e + v^2) - Where e is the number of edges and v is the number of nodes. We process all edges and
  then all possible pairs of nodes.

_ Space Complexity:

  O(e) - We maintain a graph to keep track of the connections between nodes.