Maximum Total Importance of Roads

Med

#2083Time: O(R + n log n), where `R` is the number of roads. It takes `O(R)` to compute the degrees. Sorting the `n` degrees takes `O(n log n)`. The final summation takes `O(n)`. The dominant factor is the sort.Space: O(n) to store the `degree` array for `n` cities.1 company

Patterns

Greedy

Algorithms

Sorting

Data structures

Heap (Priority Queue)Graph

Companies

Hudson River Trading

Prompt

You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.

You are also given a 2D integer array roads where roads[i] = [a_i, b_i] denotes that there exists a bidirectional road connecting cities a_i and b_i.

You need to assign each city with an integer value from 1 to n, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects.

Return the maximum total importance of all roads possible after assigning the values optimally.

Example 1:

Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output: 43
Explanation: The figure above shows the country and the assigned values of [2,4,5,3,1].
- The road (0,1) has an importance of 2 + 4 = 6.
- The road (1,2) has an importance of 4 + 5 = 9.
- The road (2,3) has an importance of 5 + 3 = 8.
- The road (0,2) has an importance of 2 + 5 = 7.
- The road (1,3) has an importance of 4 + 3 = 7.
- The road (2,4) has an importance of 5 + 1 = 6.
The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.
It can be shown that we cannot obtain a greater total importance than 43.

Example 2:

Input: n = 5, roads = [[0,3],[2,4],[1,3]]
Output: 20
Explanation: The figure above shows the country and the assigned values of [4,3,2,5,1].
- The road (0,3) has an importance of 4 + 5 = 9.
- The road (2,4) has an importance of 2 + 1 = 3.
- The road (1,3) has an importance of 3 + 5 = 8.
The total importance of all roads is 9 + 3 + 8 = 20.
It can be shown that we cannot obtain a greater total importance than 20.

Constraints:

2 <= n <= 5 * 10⁴
1 <= roads.length <= 5 * 10⁴
roads[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i
There are no duplicate roads.

Approaches

2 approaches with complexity analysis and trade-offs.

The fundamental insight to solving this problem is to understand how the assignment of values to cities affects the total importance. The total importance is the sum of importances of all roads. If we expand this sum, we find that each city's assigned value contributes to the total sum as many times as its degree (the number of roads connected to it). Therefore, the total importance can be expressed as: Total Importance = Σ (value[i] * degree[i]) for all cities i.

To maximize this sum, we should employ a greedy strategy based on the rearrangement inequality: pair the largest values with the largest degrees. This means the city with the highest degree should be assigned the value n, the city with the second-highest degree gets n-1, and so on, down to the city with the lowest degree getting the value 1.

This approach implements this strategy by first calculating all city degrees, then sorting them, and finally calculating the total sum by pairing the sorted degrees with the values 1, 2, ..., n.

Algorithm

Identify the Core Formula: The total importance of all roads is the sum of value[u] + value[v] for every road (u, v). This can be rewritten as the sum of value[city] * degree[city] for every city. The degree of a city is the number of roads connected to it.
Greedy Strategy: To maximize this sum, we must assign the largest values (from the set {1, 2, ..., n}) to the cities with the highest degrees. This is based on the rearrangement inequality.
Implementation Steps:
1. Create a degree array of size n to store the degree of each city.
2. Iterate through the roads array. For each road [u, v], increment degree[u] and degree[v].
3. Sort the degree array in ascending order. This places the smallest degrees at the beginning and the largest degrees at the end.
4. Initialize a variable totalImportance to 0.
5. Iterate through the sorted degree array. The i-th element (0-indexed) corresponds to the i-th smallest degree. Assign it the i-th smallest value, which is i + 1.
6. Add the product sorted_degree[i] * (i + 1) to totalImportance.
7. Return totalImportance.

Walkthrough

1import java.util.Arrays;2 3class Solution {4    public long maximumImportance(int n, int[][] roads) {5        // Step 1 & 2: Calculate the degree of each city.6        // Use long for degree to avoid potential overflow in intermediate calculations, though int is sufficient for degree itself.7        long[] degree = new long[n];8        for (int[] road : roads) {9            degree[road[0]]++;10            degree[road[1]]++;11        }12 13        // Step 3: Sort the degrees in ascending order.14        Arrays.sort(degree);15 16        // Step 4, 5, & 6: Calculate the total importance.17        // Assign values 1 to n to the sorted degrees.18        // The smallest degree gets value 1, second smallest gets 2, and so on.19        long totalImportance = 0;20        for (int i = 0; i < n; i++) {21            totalImportance += degree[i] * (i + 1);22        }23 24        // Step 7: Return the final result.25        return totalImportance;26    }27}

Complexity

Time

O(R + n log n), where `R` is the number of roads. It takes `O(R)` to compute the degrees. Sorting the `n` degrees takes `O(n log n)`. The final summation takes `O(n)`. The dominant factor is the sort.

Space

O(n) to store the `degree` array for `n` cities.

Trade-offs

Pros

The logic is straightforward and follows a common greedy pattern.
Relatively easy to implement using standard library sort functions.

Cons

The O(n log n) sorting step is not the most optimal solution possible and can be a bottleneck if n is very large.

This approach builds on the same greedy principle—pairing high degrees with high values—but optimizes the sorting step. A general-purpose comparison sort takes O(n log n) time. However, since the degrees are integers within a known range [0, n-1], we can use a more efficient, non-comparison-based sorting technique like Counting Sort. By counting the occurrences of each degree, we can effectively determine the sorted order of degrees in linear time.

We iterate through the possible degrees from smallest to largest. For each degree value, we assign the next available importance values (starting from 1) to all cities that have that degree. This avoids the O(n log n) bottleneck and leads to a more efficient linear time solution.

Algorithm

Calculate Degrees: First, compute the degree of each city by iterating through the roads array, similar to the previous approach. Store these in a degree array.
Count Frequencies: Instead of sorting the degree array, create a degreeCounts array of size n. degreeCounts[d] will store the number of cities with degree d. Populate this by iterating through the degree array.
Calculate Importance Sum:
1. Initialize totalImportance = 0 and value = 1.
2. Iterate through the degreeCounts array from degree d = 0 to n-1.
3. For each degree d, there are degreeCounts[d] cities. These cities with the smallest degrees will be assigned the next available smallest values.
4. Use a nested loop: for each of the degreeCounts[d] cities, add d * value to totalImportance and then increment value.
5. After iterating through all degrees, totalImportance will hold the maximum possible sum.

Walkthrough

1class Solution {2    public long maximumImportance(int n, int[][] roads) {3        // Step 1: Calculate the degree of each city.4        long[] degree = new long[n];5        for (int[] road : roads) {6            degree[road[0]]++;7            degree[road[1]]++;8        }9 10        // Step 2: Count the frequency of each degree.11        // This is effectively a linear-time sorting method (Counting Sort).12        int[] degreeCounts = new int[n];13        for (long d : degree) {14            // The degree of a city is at most n-1.15            degreeCounts[(int)d]++;16        }17 18        // Step 3: Calculate total importance using the counts.19        long totalImportance = 0;20        long value = 1;21        // Iterate through degrees from 0 to n-1.22        for (int d = 0; d < n; d++) {23            // For all cities that have degree 'd'.24            for (int i = 0; i < degreeCounts[d]; i++) {25                // Assign the next available value and add to the total importance.26                totalImportance += (long)d * value;27                value++;28            }29        }30 31        return totalImportance;32    }33}

Complexity

Time

O(R + n), where `R` is the number of roads. `O(R)` to compute degrees, `O(n)` to populate the `degreeCounts` array, and `O(n)` to calculate the final sum (the inner loop runs a total of `n` times across all iterations of the outer loop).

Space

O(n) to store the `degree` array and the `degreeCounts` array.

Trade-offs

Pros

Achieves optimal linear time complexity, making it very efficient.
Outperforms the sorting-based approach, especially for large values of n.

Cons

The logic is slightly more involved than a direct sort, requiring an extra counting step.

Solutions

Solution

1class Solution {2public3  long maximumImportance(int n, int[][] roads) {4    int[] deg = new int[n];5    for (int[] r : roads) {6      ++deg[r[0]];7      ++deg[r[1]];8    }9    Arrays.sort(deg);10    long ans = 0;11    for (int i = 0; i < n; ++i) {12      ans += (long)(i + 1) * deg[i];13    }14    return ans;15  }16}

1class Solution {2public:3  long long maximumImportance(int n, vector<vector<int>> &roads) {4    vector<int> deg(n);5    for (auto &r : roads) {6      ++deg[r[0]];7      ++deg[r[1]];8    }9    sort(deg.begin(), deg.end());10    long long ans = 0;11    for (int i = 0; i < n; ++i)12      ans += 1ll * (i + 1) * deg[i];13    return ans;14  }15};

1class Solution:2    def maximumImportance(self, n: int, roads: List[List[int]]) -> int: deg = [0] * n for a, b in roads: deg[a] += 1 deg[b] += 1 deg . sort() return sum(i * v for i, v in enumerate(deg, 1))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem