MediumNo. 1615
Maximal Network Rank — LeetCode 1615 Python Solution
- Pattern
- Depth-First Search
- Topics
- Graph
- Reading time
- 2 min
- Source
- leetcode.com
The problem
There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.
Example
- Input
- n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
- Output
- 4
- Explanation
- The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.
Python solution
class Solution:
def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
g = [[0] * n for _ in range(n)]
cnt = [0] * n
for a, b in roads:
g[a][b] = g[b][a] = 1
cnt[a] += 1
cnt[b] += 1
return max(cnt[a] + cnt[b] - g[a][b] for a in range(n) for b in range(a + 1, n))Complexity
- Time
- O(n2)
- Space · auxiliary
- O(n2)
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1615. Maximal Network Rank is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Graph.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0207 | Course Schedule | Medium |
| 0210 | Course Schedule II | Medium |
| 0310 | Minimum Height Trees | Medium |
| 0332 | Reconstruct Itinerary | Hard |
| 0399 | Evaluate Division | Medium |
| 0547 | Number of Provinces | Medium |
Frequently asked questions
- How hard is LeetCode 1615. Maximal Network Rank?
LeetCode 1615. Maximal Network Rank is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1615. Maximal Network Rank?
The Python solution on this page runs in O(n2).
- What is the space complexity of LeetCode 1615. Maximal Network Rank?
The Python solution on this page uses O(n2) auxiliary space.
- What topics does LeetCode 1615. Maximal Network Rank cover?
LeetCode 1615. Maximal Network Rank is tagged Graph on LeetCode.