Leetcode 1738 Solution

This article provides solution to leetcode question 1738 (maximal-network-rank).
Categories:
Tags:
Access this page by simply typing in "lcs 1738" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        neighbors = collections.defaultdict(set)

        for src, dst in roads:
            neighbors[src].add(dst)
            neighbors[dst].add(src)

        ans = 0
        for i, j in itertools.combinations(list(range(n)), 2):
            cnt = len(neighbors[i]) + len(neighbors[j])
            
            if j in neighbors[i]:
                cnt -= 1

            ans = max(ans, cnt)
        return ans