We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximal Network Rank

Number: 1738

Difficulty: Medium

Paid? No

Companies: smartnews, Apple, Adobe, DRW, Microsoft

Problem Description

Given n cities and an array of roads connecting pairs of these cities, the task is to determine the maximal network rank of the infrastructure. The network rank for a pair of cities is defined as the total number of roads directly connected to either city, counting a road that connects the two cities only once. The solution should return the maximum network rank considering all pairs of distinct cities.

Key Insights

  • Use an array to count the number of roads connected to each city.
  • Use a set (or equivalent) to record directly connected city pairs, so you can efficiently check if two cities have a direct road.
  • Iterate through each distinct pair of cities to compute their network rank by summing their road counts and subtracting one if they are directly connected.
  • Since n is at most 100, using a double loop over city pairs (O(n²)) is efficient enough.

Space and Time Complexity

Time Complexity: O(n²)
Space Complexity: O(n + m) where m is the number of roads (for storing connection information)

Solution

We first count the number of roads attached to each city. Meanwhile, we store each road connection in a set to quickly check if a pair of cities is directly connected. Then, we iterate over every possible pair of cities. For each pair, we calculate the network rank as the sum of their road counts and subtract one if they are directly connected. This method ensures we properly consider the shared road only once. We keep track of the maximum network rank found and return it.

Code Solutions

# Python solution for Maximal Network Rank

def maximalNetworkRank(n, roads):
    # Array to store road count (degree) for each city
    degree = [0] * n
    # Set to store each road as a tuple of connected cities (unordered)
    connected = set()
    
    # Populate degree and connected set
    for road in roads:
        city1, city2 = road[0], road[1]
        degree[city1] += 1  # Increment road count for city1
        degree[city2] += 1  # Increment road count for city2
        # Add tuple sorted to keep order consistent
        connected.add((min(city1, city2), max(city1, city2)))
    
    # Initialize maximal rank
    max_rank = 0
    # Iterate through each pair of cities
    for i in range(n):
        for j in range(i + 1, n):
            # Sum degrees of both cities
            current_rank = degree[i] + degree[j]
            # If cities i and j are directly connected, subtract 1
            if (i, j) in connected:
                current_rank -= 1
            # Update max_rank if current rank is higher
            max_rank = max(max_rank, current_rank)
    
    return max_rank

# Example usage
print(maximalNetworkRank(4, [[0,1],[0,3],[1,2],[1,3]]))  # Expected output: 4
← Back to All Questions