Skip to main content
Talentd

Maximum Total Importance of Roads - Solution & Explanation

MediumGreedyGraphSortingHeap (Priority Queue)11 min readAsked at: Hrt
Practice this problem

Problem Statement

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

In C, we manage two indices, left and right, starting from opposite ends of the array. We move the pointers towards each other based on the conditions.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

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.

In C, the qsort function is used for sorting. We then iterate over the sorted array to generate the solution.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting
Space Complexity: O(1) if we disregard sorting space

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Two-Pointer Technique

Time Complexity: O(n)
Space Complexity: O(1)

Approach 2: Sorting and Iteration

Time Complexity: O(n log n) due to sorting
Space Complexity: O(1) if we disregard sorting space

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer TechniqueO(n log n + m)O(n)When assigning explicit values to cities after sorting by degree
Sorting and IterationO(n log n + m)O(n)Clean greedy solution using degree counts and value multiplication

Video Solution

Maximum Total Importance of Roads | Thought Process | Leetcode 2285 | codestorywithMIK • codestorywithMIK • 7,906 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Total Importance of Roads with our built-in code editor and test cases.

Practice on FleetCode
Previous

Container With Most Water

Next

Wildcard Matching