Jovian
⭐️
Sign In

Maximal Network Rank

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.

Maximal Network Rank

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

How to run the code and save your work

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.

Option 1: Running using free online resources (1-click, recommended)

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.

Option 2: Running on your computer locally

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.

Saving your work

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

Problem Statement

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.

Source: Maximal Network Rank - Leetcode 1615

The Method

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

  1. State the problem clearly. Identify the input & output formats.
  2. Come up with some example inputs & outputs. Try to cover all edge cases.
  3. Come up with a correct solution for the problem. State it in plain English.
  4. Implement the solution and test it using example inputs. Fix bugs, if any.
  5. Analyze the algorithm's complexity and identify inefficiencies, if any.
  6. 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.

Solution

1. State the problem clearly. Identify the input & output formats.

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] = [ ai, bi], return the maximal network rank of the entire infrastructure.

Input

  1. n: integer, number of cities in the infrastructure
  2. roads[i] = [ ai, bi]: List representing bidirectional roads connecting cities ai and bi

Output

  1. 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

2. Come up with some example inputs & outputs. Try to cover all edge cases.

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:

  1. Input: n = 4, roads = [[0, 1], [0, 3], [1, 2], [1, 3]]
    Output: 4
  2. Input: n = 5, roads = [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]
    Output: 5
  3. Input: n = 8, roads = [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]
    Output: 5
  4. Input: n = 0, roads = [None]
    Output: 0
  5. 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.

3. Come up with a correct solution for the problem. State it in plain English.

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:

  1. Check every possible pair of n cities for connections.
  2. If a connection is found, increment counter.
  3. Get greater value between current city pair network rank vs. previous city pair network rank.
  4. Store greater value in max_rank
  5. 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

4. Implement the solution and test it using example inputs. Fix bugs, if any.

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

5. Analyze the algorithm's complexity and identify inefficiencies, if any.

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

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

maximalNetworkRank() Time Complexity Calculation:

Execution Times:

  • 3 nested for loop control statements: n3, 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.

n3 + 5 + 1 + 1 + 1
Since the highest order of n in the above equation is n3, the final Asymptotic Time Complexity is O(n3), or Cubic.

Identify Inefficiencies

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(n2). This is an inefficiency that should be optimized, if possible.

In [27]:
maximalNetworkRankTimeComplexity = 'O(n^3)'     # Cubic Asymptotic Time Complexity, O(n^3)

Asymptotic Space Complexity

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 3n: 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 n3, the final 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

6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

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

7. Come up with a correct solution for the problem. State it in plain English.

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

  1. Create an n x n matrix of all city connections from the the input list, roads[][] .
  2. Use this matrix to access each of the pairs of cities.
  3. For each city, use the matrix to count how many other cities are connected to it.
  4. Use a counter to keep track of the number of connections each city has.
  5. The highest number of connections to a city is the Maximum Network Rank.
  6. 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..

8. Implement the solution and test it using example inputs. Fix bugs, if any.

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)

9. Analyze the algorithm's complexity and identify inefficiencies, if any.

Asymptotic Time Complexity

  • The number of times eaach statement is executed

maximalNetworkRank2() Time Complexity Calculation:

Execution Times:

  • 2 nested for loop control statements: n2, 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.

n2 + n + 1 + 2 + 1 + 1 + 1
Since the highest order of n in the above equation is n2, the final Asymptotic Time Complexity is O(n2), or Quadratic.

In [ ]:
maximalNetworkRank2TimeComplexity = 'O(n^2)'     # Quadratic Asymptotic Time Complexity, O(n^2)

Asymptotic Space Complexity

  • 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: n2, 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.

n2 + 3n + n + 6
Since the highest order of n in the above equation is n2, the final Asymptotic Space Complexity of maximalNetworkRank2() is O(n2), 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")