Maximal Network Rank - Practice Coding Problems

Maximal Network Rank - Problem

Graph Medium

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.

Input & Output

Example 1 — Basic Network

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

› Output: 4

💡 Note: 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 — Simple Network

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

› Output: 5

💡 Note: There are 5 roads that are connected to either 1 or 2. Since 1 and 2 are not directly connected, we don't subtract anything.

Example 3 — No Roads

$ Input: n = 8, roads = []

› Output: 0

💡 Note: The maximal network rank is 0 since there are no roads.

Constraints

2 ≤ n ≤ 100
0 ≤ roads.length ≤ n × (n-1) / 2
roads[i].length == 2
0 ≤ a_i, b_i ≤ n-1
a_i ≠ b_i
Each pair of cities has at most one road connecting them

Visualization

Tap to expand

Understanding the Visualization

Input

Cities and roads connecting them

Calculate

For each pair: sum degrees, subtract if direct connection

Output

Maximum network rank found

Key Takeaway

🎯 Key Insight: Pre-calculate degrees for O(1) lookup, then check all pairs efficiently

Asked in

G Google 12 f Facebook 8 M Microsoft 6 a Amazon 4

The key insight is that network rank equals degree[city1] + degree[city2] - (1 if directly connected). Best approach pre-calculates degrees and uses a set for O(1) direct connection lookup. Time: O(n² + m), Space: O(n + m)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Degree Calculation + Direct Connection Check	O(n² + m)	O(n + m)	Pre-calculate each city's degree and use adjacency set for direct connections
Brute Force - Count Roads for Each Pair	O(n² × m)	O(1)	For each pair of cities, count all roads connected to either city

Optimized - Degree Calculation + Direct Connection Check — Algorithm Steps

Calculate degree for each city
Build adjacency set for O(1) direct connection lookup
For each city pair, compute rank = degree[i] + degree[j] - (direct connection ? 1 : 0)
Return maximum rank found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Degrees

Count roads per city upfront

Create Adjacency Set

Fast direct connection lookup

Calculate Ranks

Use formula: deg[i] + deg[j] - direct

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int n, int roads[][2], int roadsSize) {
    // Calculate degrees
    int* degrees = (int*)calloc(n, sizeof(int));
    
    // Build adjacency matrix for O(1) lookup
    int** adjacent = (int**)calloc(n, sizeof(int*));
    for (int i = 0; i < n; i++) {
        adjacent[i] = (int*)calloc(n, sizeof(int));
    }
    
    for (int i = 0; i < roadsSize; i++) {
        int a = roads[i][0], b = roads[i][1];
        degrees[a]++;
        degrees[b]++;
        adjacent[a][b] = 1;
        adjacent[b][a] = 1;
    }
    
    int maxRank = 0;
    
    // Check every pair of cities
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int rank = degrees[i] + degrees[j];
            // If directly connected, subtract 1 to avoid double counting
            if (adjacent[i][j]) {
                rank -= 1;
            }
            if (rank > maxRank) {
                maxRank = rank;
            }
        }
    }
    
    // Free memory
    free(degrees);
    for (int i = 0; i < n; i++) {
        free(adjacent[i]);
    }
    free(adjacent);
    
    return maxRank;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Simple parsing for [[a,b],[c,d]] format
    int roads[1000][2];
    int roadsSize = 0;
    
    char* ptr = line;
    while (*ptr && roadsSize < 1000) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            int a, b;
            sscanf(ptr, "[%d,%d]", &a, &b);
            roads[roadsSize][0] = a;
            roads[roadsSize][1] = b;
            roadsSize++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(n, roads, roadsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² + m)

O(m) to build degrees and adjacency set, O(n²) to check all pairs

⚠ Quadratic Growth

Space Complexity

O(n + m)

O(n) for degree array, O(m) for adjacency set

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Degree Calculation + Direct Connection Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler