2285. Maximum Total Importance of Roads

MediumGreedyGraphSortingHeap (Priority Queue)

Problem Description

You have a country with n cities numbered from 0 to n - 1. These cities are connected by bidirectional roads given in a 2D array roads, where roads[i] = [ai, bi] means there's a road connecting city ai and city bi.

Your task is to assign each city a unique value from 1 to n (each value used exactly once). The importance of a road is calculated as the sum of the values assigned to the two cities it connects.

The goal is to find the optimal assignment of values to cities that maximizes the total importance of all roads.

For example, if you have a road connecting city A (assigned value 3) and city B (assigned value 5), that road's importance would be 3 + 5 = 8.

The solution uses a greedy approach: cities that appear in more roads (higher degree) should be assigned higher values. This is because a city with degree d contributes its assigned value d times to the total importance. The algorithm counts each city's degree (how many roads connect to it), sorts cities by degree, and assigns values 1 through n in ascending order of degree. This ensures cities with the most connections get the highest values, maximizing the total importance.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Let's think about how each city contributes to the total importance. If a city appears in multiple roads, its assigned value gets counted multiple times - once for each road it's part of.

For instance, if city i is connected to 3 other cities (degree = 3), then whatever value we assign to city i will be added to the total importance 3 times. This means a city with degree d contributes value × d to the total importance.

The key insight is: to maximize the total importance, we should assign larger values to cities that appear in more roads. Why? Because these values get multiplied by their degree when calculating the total contribution.

Consider a simple example: if we have two cities with degrees 1 and 3, and we need to assign values 1 and 2:

Assigning value 2 to the city with degree 3: contribution = 2 × 3 = 6
Assigning value 1 to the city with degree 1: contribution = 1 × 1 = 1
Total = 7

Versus:

Assigning value 1 to the city with degree 3: contribution = 1 × 3 = 3
Assigning value 2 to the city with degree 1: contribution = 2 × 1 = 2
Total = 5

Clearly, the first assignment gives us a higher total. This naturally leads to the greedy strategy: sort cities by their degree and assign values in ascending order - smallest values to cities with lowest degree, largest values to cities with highest degree.

Learn more about Greedy, Graph, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows a straightforward greedy algorithm with these steps:

Count the degree of each city: Create an array deg of size n initialized with zeros. Iterate through the roads array, and for each road [a, b], increment both deg[a] and deg[b] by 1. This gives us the number of roads connected to each city.
Sort cities by degree: Sort the deg array in ascending order. After sorting, deg[0] contains the smallest degree, deg[1] the second smallest, and so on. Note that we lose the original city indices here, but that's fine because we only care about the degree distribution, not which specific city gets which value.
Calculate the maximum importance: Assign values 1 to n to cities in order of their sorted degrees. The city with the smallest degree gets value 1, the next gets value 2, and so on. The contribution of each city to the total importance is value × degree.

The calculation is done efficiently using enumerate(deg, 1) which pairs each degree with its assigned value (starting from 1), then multiplies them together: sum(i * v for i, v in enumerate(deg, 1)).

For example, if the sorted degrees are [1, 2, 2, 3]:

City with degree 1 gets value 1: contribution = 1 × 1 = 1
City with degree 2 gets value 2: contribution = 2 × 2 = 4
City with degree 2 gets value 3: contribution = 3 × 2 = 6
City with degree 3 gets value 4: contribution = 4 × 3 = 12
Total importance = 1 + 4 + 6 + 12 = 23

The time complexity is O(m + n log n) where m is the number of roads (for counting degrees) and n log n for sorting. The space complexity is O(n) for the degree array.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with 4 cities and the following roads:

n = 4
roads = [[0,1], [1,2], [2,3], [1,3]]

This creates a network where:

City 0 connects to: City 1 (degree = 1)
City 1 connects to: Cities 0, 2, 3 (degree = 3)
City 2 connects to: Cities 1, 3 (degree = 2)
City 3 connects to: Cities 1, 2 (degree = 2)

Step 1: Count degrees We iterate through each road and increment the degree count:

Road [0,1]: deg[0]++, deg[1]++ → deg = [1, 1, 0, 0]
Road [1,2]: deg[1]++, deg[2]++ → deg = [1, 2, 1, 0]
Road [2,3]: deg[2]++, deg[3]++ → deg = [1, 2, 2, 1]
Road [1,3]: deg[1]++, deg[3]++ → deg = [1, 3, 2, 2]

Step 2: Sort by degree Sorting the degree array: [1, 3, 2, 2] → [1, 2, 2, 3]

Step 3: Assign values and calculate importance Now we assign values 1 through 4 to cities in order of sorted degrees:

Degree 1 gets value 1: contribution = 1 × 1 = 1
Degree 2 gets value 2: contribution = 2 × 2 = 4
Degree 2 gets value 3: contribution = 3 × 2 = 6
Degree 3 gets value 4: contribution = 4 × 3 = 12

Total importance = 1 + 4 + 6 + 12 = 23

To verify this is correct, let's check what the actual road importances would be:

If city 0 (degree 1) gets value 1, city 2 (degree 2) gets value 2, city 3 (degree 2) gets value 3, and city 1 (degree 3) gets value 4:
- Road [0,1]: 1 + 4 = 5
- Road [1,2]: 4 + 2 = 6
- Road [2,3]: 2 + 3 = 5
- Road [1,3]: 4 + 3 = 7
- Total = 5 + 6 + 5 + 7 = 23 ✓

The greedy approach ensures we maximize the total by giving the highest values to the most connected cities.

Solution Implementation

1class Solution:
2    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
3        # Initialize degree array to count connections for each city
4        degree = [0] * n
5      
6        # Count the degree (number of connections) for each city
7        for city_a, city_b in roads:
8            degree[city_a] += 1
9            degree[city_b] += 1
10      
11        # Sort degrees in ascending order
12        # Cities with higher degrees will get higher importance values
13        degree.sort()
14      
15        # Calculate total importance by assigning values 1 to n
16        # Cities with lowest degree get lowest importance (1),
17        # Cities with highest degree get highest importance (n)
18        total_importance = sum(importance * deg_count for importance, deg_count in enumerate(degree, start=1))
19      
20        return total_importance
21

1class Solution {
2    public long maximumImportance(int n, int[][] roads) {
3        // Create an array to store the degree (number of connections) for each city
4        int[] degree = new int[n];
5      
6        // Calculate the degree for each city by counting how many roads connect to it
7        for (int[] road : roads) {
8            degree[road[0]]++;
9            degree[road[1]]++;
10        }
11      
12        // Sort the degrees in ascending order
13        // Cities with higher degrees should get higher importance values
14        Arrays.sort(degree);
15      
16        // Calculate the maximum total importance
17        long totalImportance = 0;
18      
19        // Assign importance values from 1 to n
20        // Cities with lowest degree get lowest importance (greedy approach)
21        for (int i = 0; i < n; i++) {
22            // Importance value is (i + 1), multiply by the degree of the city
23            totalImportance += (long)(i + 1) * degree[i];
24        }
25      
26        return totalImportance;
27    }
28}
29

1class Solution {
2public:
3    long long maximumImportance(int n, vector<vector<int>>& roads) {
4        // Create a vector to store the degree (number of connections) for each city
5        vector<int> degree(n);
6      
7        // Calculate the degree of each city by counting how many roads connect to it
8        for (const auto& road : roads) {
9            ++degree[road[0]];  // Increment degree for first city in the road
10            ++degree[road[1]];  // Increment degree for second city in the road
11        }
12      
13        // Sort degrees in ascending order to assign lower importance values to cities with fewer connections
14        sort(degree.begin(), degree.end());
15      
16        // Calculate the maximum total importance
17        long long totalImportance = 0;
18      
19        // Assign importance values 1 to n, with higher values going to cities with more connections
20        for (int i = 0; i < n; ++i) {
21            // Multiply the importance value (i + 1) by the degree of the city at position i
22            // Use 1LL to ensure the multiplication is done in long long to avoid overflow
23            totalImportance += static_cast<long long>(i + 1) * degree[i];
24        }
25      
26        return totalImportance;
27    }
28};
29

1/**
2 * Calculates the maximum importance of all roads after assigning values 1 to n to cities
3 * @param n - The number of cities
4 * @param roads - Array of road connections between cities (0-indexed)
5 * @returns The maximum total importance of all roads
6 */
7function maximumImportance(n: number, roads: number[][]): number {
8    // Initialize array to store degree (number of connections) for each city
9    const degrees: number[] = Array(n).fill(0);
10  
11    // Count the degree of each city by iterating through all roads
12    for (const [cityA, cityB] of roads) {
13        degrees[cityA]++;
14        degrees[cityB]++;
15    }
16  
17    // Sort degrees in ascending order
18    // Cities with higher degrees should get higher importance values
19    degrees.sort((a, b) => a - b);
20  
21    // Calculate total importance by assigning values 1 to n
22    // Cities with lowest degree get lowest values (1, 2, ...)
23    // Cities with highest degree get highest values (..., n-1, n)
24    return degrees.reduce((totalImportance, degree, index) => {
25        const assignedValue = index + 1; // Value assigned to this city (1 to n)
26        return totalImportance + assignedValue * degree;
27    }, 0);
28}
29

Time and Space Complexity

Time Complexity: O(n log n)

The algorithm performs the following operations:

Initializing the degree array: O(n)
Iterating through all roads to calculate degrees: O(m) where m is the number of roads (edges)
Sorting the degree array: O(n log n)
Computing the sum with enumerate: O(n)

Since the most expensive operation is sorting, and m (number of roads) is typically bounded by O(n²) in the worst case but doesn't affect the dominant sorting term, the overall time complexity is O(n log n).

Space Complexity: O(n)

The algorithm uses:

The degree array deg of size n: O(n)
The sorting operation uses O(1) extra space for Python's Timsort (in-place for lists)
The generator expression in the sum doesn't create an additional list: O(1)

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Track Original City Indices

A common mistake is trying to maintain the original city indices while sorting, thinking you need to know which specific city gets which value. This leads to unnecessarily complex code:

# Overcomplicated approach - AVOID THIS
degree_with_index = [(deg, i) for i, deg in enumerate(degree)]
degree_with_index.sort()
assignment = [0] * n
for importance, (deg, city_idx) in enumerate(degree_with_index, 1):
    assignment[city_idx] = importance
# Then calculate total...

Why it's wrong: The problem doesn't ask for the specific assignment of values to cities - it only asks for the maximum total importance. Since we're summing up all contributions, we only need the degree distribution, not the mapping.

Correct approach: Simply sort the degrees and calculate directly, as shown in the solution.

2. Misunderstanding the Importance Calculation

Some might incorrectly calculate the importance by thinking each road's importance is counted once:

# INCORRECT - counting each road's importance separately
total = 0
for a, b in roads:
    total += assignment[a] + assignment[b]

Why it's wrong: This double-counts the contribution correctly but misses the optimization insight. The key realization is that each city contributes its value exactly degree times to the total.

Correct understanding: A city with value v and degree d contributes v × d to the total importance, which is why we calculate sum(importance * deg_count for importance, deg_count in enumerate(degree, 1)).

3. Off-by-One Errors with Value Assignment

A subtle mistake is using 0-based indexing for values instead of 1-based:

# WRONG - assigns values 0 to n-1 instead of 1 to n
total_importance = sum(i * deg for i, deg in enumerate(degree))

Impact: This would assign values starting from 0, which violates the problem constraint that values must be from 1 to n. The result would be less than optimal since we're "wasting" the value 0 on the city with the lowest degree.

Solution: Use enumerate(degree, start=1) to ensure values start from 1.

4. Not Handling Edge Cases

Failing to consider edge cases like:

Empty roads array (isolated cities)
n = 1 (single city with no roads)

# Better implementation with edge case consideration
if not roads:  # All cities are isolated
    return 0
if n == 1:
    return 0

However, the original solution handles these naturally since isolated cities have degree 0 and contribute 0 to the sum regardless of their assigned value.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know