Learn data science and machine learning by building real-world projects on Jovian

Sign up to execute **data-structures-and-algorithms-python-project** and 160,000+ data science projects. Build your own projects and share them online!

Updated 5 months ago

The **maximal network rank** of an infrastructure of `n`

cities with some number of `roads`

is the **maximum network rank** of all pairs of different cities. Given the integer `n`

and the array `roads`

, return the **maximal network rank** of the entire infrastructure.

*To learn how to use this template, check out the course "Data Structures and Algorithms in Python".*

The recommended way to run this notebook is to click the "Run" button at the top of this page, and select "Run on Binder". This will run the notebook on mybinder.org, a free online service for running Jupyter notebooks.

This tutorial is an executable Jupyter notebook. You can *run* this tutorial and experiment with the code examples in a couple of ways: *using free online resources* (recommended) or *on your computer*.

The easiest way to start executing the code is to click the **Run** button at the top of this page and select **Run on Binder**. You can also select "Run on Colab" or "Run on Kaggle", but you'll need to create an account on Google Colab or Kaggle to use these platforms.

To run the code on your computer locally, you'll need to set up Python, download the notebook and install the required libraries. We recommend using the Conda distribution of Python. Click the **Run** button at the top of this page, select the **Run Locally** option, and follow the instructions.

Before staring the assignment, let's save a snapshot of the assignment to your Jovian profile, so that you can access it later, and continue your work.

In [2]:

`project_name = 'data-structures-and-algorithms-python-project' `

In [3]:

`!pip install jovian --upgrade --quiet`

In [4]:

`import jovian`

In [5]:

`jovian.commit(project=project_name)`

```
[jovian] Detected Colab notebook...
[jovian] Please enter your API key ( from https://jovian.ai/ ):
API KEY: ··········
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project
```

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.

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

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

Example 1:

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.

Example 2:

Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]] Output: 5 Explanation: There are 5 roads that are connected to cities 1 or 2.

Example 3:

Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]] Output: 5 Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.

Constraints:

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

Here's the systematic strategy we'll apply for solving problems:

- State the problem clearly. Identify the input & output formats.
- Come up with some example inputs & outputs. Try to cover all edge cases.
- Come up with a correct solution for the problem. State it in plain English.
- Implement the solution and test it using example inputs. Fix bugs, if any.
- Analyze the algorithm's complexity and identify inefficiencies, if any.
- Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

This approach is explained in detail in Lesson 1 of the course. Let's apply this approach step-by-step.

While this problem is stated clearly enough, it's always useful to try and express in your own words, in a way that makes it most clear for you.

**Problem**

The network rank of two different cities is the total number of directly connected roads to either city. The`maximal network rank`

of the infrastructure is the`maximum network rank`

of all possible pairs of different cities. Given the integer`n`

for the number of cities in the infrastructure and the array roads[i] = [ a_{i}, b_{i}], return the`maximal network rank`

of the entire infrastructure.

**Input**

`n`

: integer, number of cities in the infrastructure`roads[i]`

= [ a_{i}, b_{i}]: List representing bidirectional roads connecting cities a_{i}and b_{i}

**Output**

`max_rank`

: The maximal network rank of all pairs of different cities in the entire infrastructure.

Based on the above, we can now create a signature of our function:

In [6]:

```
from typing import List
# function signature
def maximalNetworkRank(n: int, roads: List[List[int]]) -> int:
pass
```

Save and upload your work before continuing.

In [7]:

`import jovian`

In [8]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project
```

Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter:

**Input: n = 4, roads = [[0, 1], [0, 3], [1, 2], [1, 3]]**

Output: 4**Input: n = 5, roads = [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]**

Output: 5**Input: n = 8, roads = [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]**

Output: 5**Input: n = 0, roads = [None]**

Output: 0**Input: n = 2, roads = [[0, 1], [1, 0]]**

Output: 1

We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: `input`

(a dictionary itself containing one key for each argument to the function and `output`

(the expected result from the function).

In [9]:

```
test = {
'input': {
'n': 4,
'roads': [[0,1], [0, 3], [1, 2], [1, 3]]
},
'output': 4
}
```

In [10]:

`from jovian.pythondsa import evaluate_test_case`

Create one test case for each of the scenarios listed above. We'll store our test cases in an array called `tests`

.

In [11]:

```
# initialize empty list of test cases
tests = []
```

In [12]:

```
# add a test case to the empty list of test cases
tests.append(test)
```

In [13]:

```
tests.append({
'input': {
'n': 5,
'roads': [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]
},
'output': 5
})
```

In [14]:

```
# add more test cases
tests.append({
'input': {
'n': 8,
'roads': [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]
},
'output': 5
})
```

In [15]:

```
# add more test cases
tests.append({
'input': {
'n': 0,
'roads': [None]
},
'output': 0
})
```

In [16]:

```
# add more test cases
tests.append({
'input': {
'n': 1,
'roads': [[0, 1]]
},
'output': 0
})
```

In [17]:

```
# add more test cases
tests.append({
'input': {
'n': 2,
'roads': [[0, 1], [1, 0]]
},
'output': 1
})
```

In [18]:

`from jovian.pythondsa import evaluate_test_cases`

In [19]:

`evaluate_test_cases(maximalNetworkRank, tests)`

```
TEST CASE #0
Input:
{'n': 4, 'roads': [[0, 1], [0, 3], [1, 2], [1, 3]]}
Expected Output:
4
Actual Output:
None
Execution Time:
0.004 ms
Test Result:
FAILED
TEST CASE #1
Input:
{'n': 5, 'roads': [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]}
Expected Output:
5
Actual Output:
None
Execution Time:
0.002 ms
Test Result:
FAILED
TEST CASE #2
Input:
{'n': 8, 'roads': [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]}
Expected Output:
5
Actual Output:
None
Execution Time:
0.002 ms
Test Result:
FAILED
TEST CASE #3
Input:
{'n': 0, 'roads': [None]}
Expected Output:
0
Actual Output:
None
Execution Time:
0.001 ms
Test Result:
FAILED
TEST CASE #4
Input:
{'n': 1, 'roads': [[0, 1]]}
Expected Output:
0
Actual Output:
None
Execution Time:
0.001 ms
Test Result:
FAILED
TEST CASE #5
Input:
{'n': 2, 'roads': [[0, 1], [1, 0]]}
Expected Output:
1
Actual Output:
None
Execution Time:
0.002 ms
Test Result:
FAILED
SUMMARY
TOTAL: 6, PASSED: 0, FAILED: 6
```

Out[19]:

```
[(None, False, 0.004),
(None, False, 0.002),
(None, False, 0.002),
(None, False, 0.001),
(None, False, 0.001),
(None, False, 0.002)]
```

Verify that all the test cases were evaluated. We expect them all to fail, since we haven't implemented the function yet.

Our first goal should always be to come up with a *correct* solution to the problem, which may not necessarily be the most *efficient* solution. Come with a correct solution and explain it in simple words below:

**Check every possible pair of**`n`

cities for connections.**If a connection is found, increment counter.****Get greater value between current city pair network rank vs. previous city pair network rank.****Store greater value in**`max_rank`

**Return**`max_rank`

Let's save and upload our work before continuing.

In [20]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project
```

In [21]:

```
# Max Network Rank
# Solution 1
# Time Complexity: O(n^3), or cubic
# Space Complexity: O(n), or linear
from typing import List
def maximalNetworkRank(n: int, roads: List[List[int]]) -> int:
# edge cases
# No roads or just one road to check
if roads == None or len(roads) <= 1 :
return 0
# Exactly 2 cities
if n == 2:
return 1
# Number of cities is zero or one
if n < 2:
return 0
max_rank = 0 # initialize the maximum network rank count to 0
# loop through each pair of cities/vertices and check for city-to-city connections
# check city i with each of the other cities for connections
for i in range(n):
# check each of the other cities for connection to city i
for j in range(i+1, n):
edge_cnt = 0 # initialize road tally, number of edges
# check for a connection between city i and city j in roads[[]]
for city in roads:
# look for any roads connected to a city
if city[0] == i or city[0] == j or city[1] == i or city[1] == j:
edge_cnt += 1 # conneection found, count it
max_rank = max(max_rank, edge_cnt) # get the largest of max_rank and edge_cnt
return max_rank
```

We can test the function by passing the input to it directly or by using the `evaluate_test_case`

function from `jovian`

.

In [22]:

`from jovian.pythondsa import evaluate_test_case`

In [23]:

`evaluate_test_case(maximalNetworkRank, test)`

```
Input:
{'n': 4, 'roads': [[0, 1], [0, 3], [1, 2], [1, 3]]}
Expected Output:
4
Actual Output:
4
Execution Time:
0.02 ms
Test Result:
PASSED
```

Out[23]:

`(4, True, 0.02)`

Evaluate your function against all the test cases together using the `evaluate_test_cases`

(plural) function from `jovian`

.

In [24]:

`from jovian.pythondsa import evaluate_test_cases`

In [25]:

`evaluate_test_cases(maximalNetworkRank, tests)`

```
TEST CASE #0
Input:
{'n': 4, 'roads': [[0, 1], [0, 3], [1, 2], [1, 3]]}
Expected Output:
4
Actual Output:
4
Execution Time:
0.022 ms
Test Result:
PASSED
TEST CASE #1
Input:
{'n': 5, 'roads': [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]}
Expected Output:
5
Actual Output:
5
Execution Time:
0.055 ms
Test Result:
PASSED
TEST CASE #2
Input:
{'n': 8, 'roads': [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]}
Expected Output:
5
Actual Output:
5
Execution Time:
0.097 ms
Test Result:
PASSED
TEST CASE #3
Input:
{'n': 0, 'roads': [None]}
Expected Output:
0
Actual Output:
0
Execution Time:
0.003 ms
Test Result:
PASSED
TEST CASE #4
Input:
{'n': 1, 'roads': [[0, 1]]}
Expected Output:
0
Actual Output:
0
Execution Time:
0.004 ms
Test Result:
PASSED
TEST CASE #5
Input:
{'n': 2, 'roads': [[0, 1], [1, 0]]}
Expected Output:
1
Actual Output:
1
Execution Time:
0.004 ms
Test Result:
PASSED
SUMMARY
TOTAL: 6, PASSED: 6, FAILED: 0
```

Out[25]:

```
[(4, True, 0.022),
(5, True, 0.055),
(5, True, 0.097),
(0, True, 0.003),
(0, True, 0.004),
(1, True, 0.004)]
```

Verify that all the test cases were evaluated. We expect them all to fail, since we haven't implemented the function yet.

Let's save our work before continuing.

In [26]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project
```

Big O notation is used here to give us an upper limit of the execution time (worst-case inputs). For larger values of `n`

, the constant values become negligible. Therefore, when a program contains a control statement, the complexities of assignment, arithmetic, logical and return statements can be ignored.

Asymptotic Time Complexity is the number of times eaach statement is executed.

`maximalNetworkRank()`

Time Complexity Calculation:Execution Times:

- 3 nested
`for loop`

control statements:`n`

^{3}, Cubic - 5 assignment operation statements: 5, Constant
- 1 logical operation statement: 1, Constant
- 1 arithmetic operation statement: 1, Constant
- 3 return statements, only 1 will execute: 1, Constant

For calculation simplicity, assume 1 byte of memory for each variable data type.

`n`

^{3}+ 5 + 1 + 1 + 1

Since the highest order of`n`

in the above equation is`n`

^{3}, thefinal Asymptotic Time Complexity is O(`n`

^{3}), or Cubic.

In the Worst Case, to find all possible connected `cities`

requires iterating through a `for loop`

for n `cities`

. For each of the `n cities`

, compare that current city with every other `city`

to determine if the pair of `cities`

are connected. This operation is implemented with a nested `for loop`

which has a **Time Complexity** of **O(n ^{2})**. This is an

In [27]:

`maximalNetworkRankTimeComplexity = 'O(n^3)' # Cubic Asymptotic Time Complexity, O(n^3)`

*Space complexity* is the total amount of memory space used by an algorithm or program, including the space of input values used during execution. The less *space* that is occupied by the variables, the faster the program will execute.

`maximalNetworkRank()`

Space Complexity Calculation:Memory Space Used:

- 6 integer variables: 6, Constant
- 1 list object of size 3
`n`

: 3n, Linear

For calculation simplicity, assume 1 byte of memory for each variable data type.

`n`

+`6`

Since the highest order of n in the above equation is`n`

^{3}, thefinal Asymptotic Space Complexity of`maximalNetworkRank()`

is O(n), or Linear.

In [28]:

`maximalNetworkRankSpaceComplexity = 'O(n)' # Linear Asymptotic Space Complexity, O(n) `

In [29]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project
```

One of the nested `for loops`

can be eliminated if a `n x n`

matrix is created and used to store all of the bidirectional `roads[][]`

. This matrix can then be used to access the connected `cities`

directly. Accessing a matrix takes just constant time which is much better timewise than iterating through a `for loop`

to find each of the connected `cities`

.

In [30]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project
```

Come with the optimized correct solution and explain it in simple words below:

**Create an n x n matrix of all**`city`

connections from the the input list,`roads[][]`

.**Use this matrix to access each of the pairs of**`cities`

.**For each**`city`

, use the matrix to count how many other`cities`

are connected to it.**Use a counter to keep track of the number of connections each**`city`

has.**The highest number of connections to a**`city`

is the Maximum Network Rank.**Return the***Maximum Network Rank*

Let's save and upload our work before continuing.

In [ ]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
```

In [ ]:

```
# Maximal Network Rank
# Solution 2: Optimized from Solution 1
# Time Complexity: O(n^3), or cubic
# Space Complexity: O(n), or linear
from typing import List
def maximalNetworkRank2(n: int, roads: List[List[int]]) -> int:
# edge cases
# No roads or just one road to check
if roads == None or len(roads) <= 1 :
return 0
# Exactly 2 cities
if n == 2:
return 1
# Number of cities is zero or one
if n < 2:
return 0
# Create an n x n matrix initialized to False to represent a graph of the cities and connecting roads
city_g = [[False] * n for i in range(n)]
# city_g = [[False for i in range(n)] * n]
# populate the n x n matrix, city_g[][], with the given list of roads, roads: [[]]
# connect pairs of cities with the corresponding bidirectional edge from roads: List[List[int]]
for a, b in roads:
city_g[a][b] = city_g[b][a] = True # connect bidirection roads
rd_count = [0] * n # count number of roads in each city
# go to each road
# get the first city and the second city
# increment the road count for each city
for r in roads:
rd_count[r[0]] += 1
rd_count[r[1]] += 1
# set them equal to each other, bidirectional
city_g[r[0]][r[1]] = True
city_g[r[1]][r[0]] = True
max_rank = 0 # initialize max_rank count
# match each city with every other city
for i in range(n):
for j in range(i+1, n):
if i != j :
max_rank = max(max_rank, rd_count[i] + rd_count[j] - (1 if city_g[i][j] else 0))
return max_rank
```

In [ ]:

```
# initialize empty list of test cases
tests2 = []
```

In [ ]:

```
# add a test case to the empty list of test cases
tests2.append(test)
```

In [ ]:

```
tests2.append({
'input': {
'n': 5,
'roads': [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]
},
'output': 5
})
```

In [ ]:

```
# add more test cases
tests2.append({
'input': {
'n': 8,
'roads': [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]
},
'output': 5
})
```

In [ ]:

```
# add more test cases
tests2.append({
'input': {
'n': 0,
'roads': [None]
},
'output': 0
})
```

In [ ]:

```
# add more test cases
tests2.append({
'input': {
'n': 1,
'roads': [[0, 1]]
},
'output': 0
})
```

In [ ]:

```
# add more test cases
tests2.append({
'input': {
'n': 2,
'roads': [[0, 1], [1, 0]]
},
'output': 1
})
```

In [ ]:

`evaluate_test_cases(maximalNetworkRank2, tests2)`

- The number of times eaach statement is executed

`maximalNetworkRank2()`

Time Complexity Calculation:Execution Times:

- 2 nested
`for loop`

control statements:`n`

^{2}, Quadratic - 1 for loop control statement:
`roads`

=>`n`

, Linear - 1 1-D array of size n declaration statement : 1, Constant
- 2 assignment declaration statements: 2, Constant
- 3 logical operation statements, only 1 will execute: 1, Constant
- 1 arithmetic operation statements: 1, Constant
- 4 return statements, only 1 will execute: 1,Constant

For calculation simplicity, assume 1 byte of memory for each variable data type.

`n`

^{2}+`n`

+ 1 + 2 + 1 + 1 + 1

Since the highest order of`n`

in the above equation is`n`

^{2}, thefinal Asymptotic Time Complexity is O(`n`

^{2}), or Quadratic.

In [ ]:

`maximalNetworkRank2TimeComplexity = 'O(n^2)' # Quadratic Asymptotic Time Complexity, O(n^2)`

- The amount of
**memory space**all of the variables of the function use

`maximalNetworkRank2()`

Space Complexity Calculation:Memory Space Used:

- 1 n x n matrix:
`n`

^{2}, quadratic - 1 List[List[int]] object of size
`3n`

:`3n`

, linear - 1 integer array of size
`n`

:`n`

, linear - 6 integer variable declaraation statements: 6 , constant

For calculation simplicity, assume 1 byte of memory for each variable data type.

`n`

^{2}+ 3`n`

+`n`

+ 6

Since the highest order of`n`

in the above equation is`n`

^{2}, thefinal Asymptotic Space Complexity of`maximalNetworkRank2()`

is O(`n`

^{2}), or Quadratic.

In [ ]:

`maximalNetworkRank2SpaceComplexity = 'O(n^2)' # Linear Asymptotic Space Complexity, O(n^2)`

If you found the problem on an external platform, you can make a submission to test your solution.

Share your approach and start a discussion on the Jovian forum: https://jovian.ai/forum/c/data-structures-and-algorithms-in-python/78

In [ ]:

`jovian.commit()`

In [ ]:

`jovian.submit(assignment="pythondsa-project")`