# Maximum Total Importance of Roads
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-total-importance-of-roads)
Canonical: https://scaleengineer.com/dsa/problems/maximum-total-importance-of-roads
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Heap (Priority Queue), Graph
**Companies:** [Hudson River Trading](https://scaleengineer.com/companies/hudson-river-trading)
---
## Problem
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] = [ai, bi]` denotes that there exists a **bidirectional** road connecting cities `ai` and `bi`.

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:**

![](https://assets.glich.co/dsa/maximum-total-importance-of-roads/image0.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-total-importance-of-roads/image1.png) 

**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 * 104`
* `1 <= roads.length <= 5 * 104`
* `roads[i].length == 2`
* `0 <= ai, bi <= n - 1`
* `ai != bi`
* There are no duplicate roads.

# Approaches
## Greedy Approach with Sorting
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`.
**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.
**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.
### Explanation
```java
import java.util.Arrays;

class Solution {
    public long maximumImportance(int n, int[][] roads) {
        // Step 1 & 2: Calculate the degree of each city.
        // Use long for degree to avoid potential overflow in intermediate calculations, though int is sufficient for degree itself.
        long[] degree = new long[n];
        for (int[] road : roads) {
            degree[road[0]]++;
            degree[road[1]]++;
        }

        // Step 3: Sort the degrees in ascending order.
        Arrays.sort(degree);

        // Step 4, 5, & 6: Calculate the total importance.
        // Assign values 1 to n to the sorted degrees.
        // The smallest degree gets value 1, second smallest gets 2, and so on.
        long totalImportance = 0;
        for (int i = 0; i < n; i++) {
            totalImportance += degree[i] * (i + 1);
        }

        // Step 7: Return the final result.
        return totalImportance;
    }
}
```
### 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`.

## Optimized Greedy Approach with Counting
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.
**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.
**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.
### Explanation
```java
class Solution {
    public long maximumImportance(int n, int[][] roads) {
        // Step 1: Calculate the degree of each city.
        long[] degree = new long[n];
        for (int[] road : roads) {
            degree[road[0]]++;
            degree[road[1]]++;
        }

        // Step 2: Count the frequency of each degree.
        // This is effectively a linear-time sorting method (Counting Sort).
        int[] degreeCounts = new int[n];
        for (long d : degree) {
            // The degree of a city is at most n-1.
            degreeCounts[(int)d]++;
        }

        // Step 3: Calculate total importance using the counts.
        long totalImportance = 0;
        long value = 1;
        // Iterate through degrees from 0 to n-1.
        for (int d = 0; d < n; d++) {
            // For all cities that have degree 'd'.
            for (int i = 0; i < degreeCounts[d]; i++) {
                // Assign the next available value and add to the total importance.
                totalImportance += (long)d * value;
                value++;
            }
        }

        return totalImportance;
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
public
  long maximumImportance(int n, int[][] roads) {
    int[] deg = new int[n];
    for (int[] r : roads) {
      ++deg[r[0]];
      ++deg[r[1]];
    }
    Arrays.sort(deg);
    long ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += (long)(i + 1) * deg[i];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumImportance(int n, vector<vector<int>> &roads) {
    vector<int> deg(n);
    for (auto &r : roads) {
      ++deg[r[0]];
      ++deg[r[1]];
    }
    sort(deg.begin(), deg.end());
    long long ans = 0;
    for (int i = 0; i < n; ++i)
      ans += 1ll * (i + 1) * deg[i];
    return ans;
  }
};

```

### Python

```python
class Solution:
    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))

```