Maximum Total Importance of Roads solution and explanation
9 more videos on this problem
Maximum Total Importance of Roads | Thought Process | Leetcode 2285 | codestorywithMIKcodestorywithMIK · 22:00 · 7K views
Maximum Total Importance of Roads - Leetcode 2285 - PythonNeetCodeIO · 9:59 · 6K views
2285. Maximum Total Importance of Roads | Greedy | Indegree OutDegree | GraphAryan Mittal · 11:34 · 3K views
2285 Maximum Total Importance of Roads Leetcode| Leetcode Biweekly Contest 79Ashutosh sharma · 10:54 · 2K views
2285. Maximum Total Importance of Roads (Leetcode Medium)Programming Live with Larry · 9:48 · 1K views
Leetcode | 2285. Maximum Total Importance of RoadsDev what excites · 11:34 · 271 views
2285. Maximum Total Importance of RoadsTop SWE · 2:23 · 194 views
LeetCode 2285 | Maximum Total Importance of Roads | #leetcodedailychallenge #graphs #greedy #sortingAlgo Horizon · 14:30 · 169 views
2285. Maximum Total Importance of Roads | Leetcode DailyLeetcode gladiators · 10:17 · 155 views
2285. Maximum Total Importance of Roadshookud · 5:08 · 85 views
The 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:
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 * 1041 <= roads.length <= 5 * 104roads[i].length == 20 <= ai, bi <= n - 1ai != bi- There are no duplicate roads.
Approach overview
Problem Overview: You have n cities connected by roads. Each city must be assigned a unique value from 1..n. The importance of a road equals the sum of the values of its two endpoints. The goal is to assign values so the total importance of all roads is maximized.
Approach 1: Two-Pointer Technique (O(n log n + m) time, O(n) space)
The key observation is that cities appearing in more roads contribute more times to the total importance. Start by computing the degree of each city (how many roads connect to it). Sort cities by degree. Now you want the largest labels assigned to the highest-degree cities. Using a two-pointer style assignment after sorting, place the smallest values at the start of the sorted list and the largest values at the end. Iterate through the roads and accumulate value[u] + value[v]. Degree counting takes O(m), sorting cities takes O(n log n), and the final accumulation is O(m). This approach uses a greedy strategy on a graph structure.
Approach 2: Sorting and Iteration (O(n log n + m) time, O(n) space)
This approach focuses directly on degrees and avoids storing explicit city-value mappings during assignment. First compute the degree of each city using a single pass over the roads. Sort the degree array in ascending order using sorting. Then assign values from 1 to n in sorted order and compute the contribution as degree[i] * assignedValue. Each city contributes its assigned value once per connected road, so multiplying by its degree accounts for all edges touching it. The final answer is the sum of these contributions. This greedy ordering guarantees that the most connected cities receive the largest labels.
Both approaches rely on the same greedy insight: maximize the contribution of frequently used nodes by giving them larger weights. A heap (priority queue) could also prioritize cities by degree, but sorting is simpler and equally efficient here.
Recommended for interviews: The sorting and iteration method is the expected solution. It demonstrates recognition of the greedy property: road contributions depend only on node degrees. Counting degrees and assigning labels after sorting shows strong algorithmic intuition and keeps the implementation short and clean.
Approach 1: Approach 1: Two-Pointer Technique
This approach utilizes the two-pointer technique to efficiently solve the problem. By keeping track of two pointers and adjusting them based on certain conditions, we can achieve the desired solution in a more efficient manner.
def solve(arr):
left, right = 0, len(arr) - 1
while left < right:
# Implement the solution using two-pointer here
left += 1
right -= 1public void solve(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
// Implement the solution using two-pointer here
left++;
right--;
}
}void solve(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while (left < right) {
// Implement the solution using two-pointer here
left++;
right--;
}
}function solve(arr) {
let left = 0, right = arr.length - 1;
while (left < right) {
// Implement the solution using two-pointer here
left++;
right--;
}
}void solve(int arr[], int n) {
int left = 0, right = n - 1;
while (left < right) {
// Implement the solution using two-pointer here
left++;
right--;
}
}void Solve(int[] arr) {
int left = 0, right = arr.Length - 1;
while (left < right) {
// Implement the solution using two-pointer here
left++;
right--;
}
}In Python, we apply the two-pointer technique with simple iteration through list indices.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Approach 2: Sorting and Iteration
This approach involves first sorting the input data, then iterating through it to construct the solution. The sorted nature of the data can simplify the logic needed for solving the problem.
def solve(arr):
arr.sort()
for val in arr:
# Build solution using sorted array
passimport java.util.Arrays;
public void solve(int[] arr) {
Arrays.sort(arr);
for (int val : arr) {
// Build solution using sorted array
}
}#include <algorithm>
void solve(std::vector<int>& arr) {
std::sort(arr.begin(), arr.end());
for (int val : arr) {
// Build solution using sorted array
}
}function solve(arr) {
arr.sort((a, b) => a - b);
for (let val of arr) {
// Build solution using sorted array
}
}#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
void solve(int arr[], int n) {
qsort(arr, n, sizeof(int), compare);
for (int i = 0; i < n; i++) {
// Build solution using sorted array
}
}using System;
void Solve(int[] arr) {
Array.Sort(arr);
foreach (int val in arr) {
// Build solution using sorted array
}
}Python's in-built sort method is utilized. Post-sorting, we iterate using a simple loop.
Time Complexity: O(n log n) due to sorting
Space Complexity: O(1) if we disregard sorting space
Approach 3: Greedy + Sorting
We consider the contribution of each city to the total importance of all roads, recorded in the array deg. Then, we sort deg by contribution from smallest to largest and allocate [1, 2, ..., n] to the cities in order.
The time complexity is O(n log n), and the space complexity is O(n).
function maximumImportance(n: number, roads: number[][]): number {
const deg: number[] = Array(n).fill(0);
for (const [a, b] of roads) {
++deg[a];
++deg[b];
}
deg.sort((a, b) => a - b);
return deg.reduce((acc, cur, idx) => acc + (idx + 1) * cur, 0);
}func maximumImportance(n int, roads [][]int) (ans int64) {
deg := make([]int, n)
for _, r := range roads {
deg[r[0]]++
deg[r[1]]++
}
sort.Ints(deg)
for i, x := range deg {
ans += int64(x) * int64(i+1)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Technique | Time Complexity: O(n) |
| Approach 2: Sorting and Iteration | Time Complexity: O(n log n) due to sorting |
| Greedy + Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n log n + m) | O(n) | When assigning explicit values to cities after sorting by degree |
| Sorting and Iteration | O(n log n + m) | O(n) | Clean greedy solution using degree counts and value multiplication |
Frequently asked questions
Is Maximum Total Importance of Roads easy or hard?
This problem is rated Medium on LeetCode. The implementation is straightforward once you recognize the greedy insight that higher-degree cities should receive higher values. The challenge lies in identifying the degree-based optimization.
Maximum Total Importance of Roads Python/Java solution
Python and Java implementations follow the same steps: build a degree array, sort it, assign values from 1 to n, and sum degree[i] * assignedValue. Python typically uses list sorting, while Java uses Arrays.sort. Both achieve O(n log n + m) complexity.
How to solve Maximum Total Importance of Roads in O(n)?
A strict O(n) solution is difficult because cities must be ordered by degree. Sorting typically costs O(n log n). However, if the degree range is small, counting sort or bucket techniques could reduce the sorting cost and approach linear time.
What is the best approach for Maximum Total Importance of Roads?
The optimal approach is a greedy strategy based on city degrees. Count how many roads connect to each city, sort cities by degree, and assign the largest values to the most connected cities. This maximizes the repeated contribution of high-degree nodes. The overall complexity is O(n log n + m).
Is Maximum Total Importance of Roads asked at Google/Amazon/Meta?
Greedy graph problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The pattern of assigning weights based on node degree is a common interview concept that tests graph reasoning and greedy optimization.
What data structure is used in Maximum Total Importance of Roads?
The main structure is an array for storing node degrees in the graph. Sorting the degree array determines which cities receive the largest values. Some implementations may also use a heap (priority queue) to repeatedly pick the highest-degree node.
What is the time complexity of Maximum Total Importance of Roads?
The standard solution runs in O(n log n + m) time. Computing degrees requires O(m), sorting the cities by degree requires O(n log n), and calculating the final importance also takes O(m). Space complexity is O(n) for storing the degree array and assigned values.