Maximal Network Rank

View Maximal Network Rank on LeetCode

Statistics

Time Spent Coding
10 minutes

Time Complexity
O(n²) - Each possible pair in the graph must be visited, resulting in the O(n²) time complexity.

Space Complexity
O(nⁿ) - In the worst case, each node is connected, making each node stored n times, resulting in the O(nⁿ) space complexity.

Runtime Beats
68.91% of other submissions

Explanation

Comments explain the algorithm

Solution

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