Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Maximal Network Rank (medium)
On this page

Problem Statement

Examples

Try it yourself

Problem Statement

You are given an infrastructure with n cities and several roads connecting these cities. Each road connects two cities bidirectionally, represented by an array roads where roads[i] = [ai, bi] signifies a road between city ai and city bi.

The network rank of two different cities is the total number of roads connected to either city. If a road connects both cities, it is counted only once.

Find the maximum network rank among all possible pairs of different cities.

Examples

Example 1:

  • Input: n = 4, roads = [[0, 2], [0, 3], [1, 2], [1, 3]]
  • Expected Output: 4
Image
  • Explanation: City 0 and City 1 each have 2 roads connecting to them. So, the maximal network rank is 4.

Example 2:

  • Input: n = 5, roads = [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3]]
  • Expected Output: 5
Image
  • Explanation: City 1 and City 3 each have 3 roads connecting to them. The road between City 1 and City 3 is counted only once. So, the maximal network rank is 5.

Example 3:

  • Input: n = 3, roads = [[0, 1], [0, 2], [1, 2]]
  • Expected Output: 3
  • Explanation: City 0 and City 1 each have 2 roads connecting to them. The road between City 1 and City 2 is counted only once. So, the maximal network rank is 3.

Constraints:

  • 2 <= n <= 100
  • 0 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 2
  • 0 <= a<sub>i</sub>, b<sub>i</sub> <= n-1
  • a<sub>i</sub> != b<sub>i</sub>
  • Each pair of cities has at most one road connecting them.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself