2285. Maximum Total Importance of Roads

MediumGreedyGraphSortingHeap (Priority Queue)
Leetcode Link

Problem Description

In this LeetCode problem, we are tasked with assigning values to cities such that the total importance of all roads is maximized. Each city is represented by an integer from 0 to n - 1, where n is the total number of cities. There is also a list of roads represented as pairs [a_i, b_i], which corresponds to a bidirectional road between cities a_i and b_i. The importance of a single road is the sum of the values assigned to the two cities it connects.

Constraints of the Problem:

  • Each city must be assigned a unique value from 1 to n, and no value may be used more than once.
  • The goal is to find an assignment of values that results in the highest possible total road importance, which is the sum of importances of all individual roads.

We need to find the optimal way to assign these values in order to achieve the maximum total importance of all roads.

Intuition

A key observation for this problem is that roads connected to cities with high degrees of connectivity (i.e., cities with many incoming and outgoing roads) should be assigned higher values in order to maximize the total importance. The reasoning is that a high-value city will contribute its value to the total importance of the network multiple times โ€“ once for each road it is connected to.

To derive an optimal solution, we can follow these steps:

  1. Calculate the degree of each city, which is the number of roads connected to it.
  2. Sort the cities based on their degree in non-decreasing order. This ensures that cities with the most roads are considered last.
  3. Assign values starting from 1 to n based on the sorted degrees; cities with lower degrees get lower values and those with higher degrees get higher values.
  4. Calculate the sum of the importance for each road using the assigned values.

This approach works because it maximizes the contribution of the most connected cities to the total road importance by ensuring that they are assigned the highest possible values.

The provided solution code implements this strategy effectively by first initializing an array deg to keep track of the degree for each city. It then iterates over the list of roads, incrementing the degree of each connected city. After sorting the deg array, it uses a simple loop to sum up the product of each value with its corresponding degree. By starting the enumeration from 1, we ensure that the lowest value assigned to cities is 1 and it goes up to n, as per the constraints.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The solution approach can be broken down into the following steps:

  1. Initialization: A list deg of length n is initialized to store the degree of each city. The degree of a city is defined as the number of roads that connect it to other cities.

    1deg = [0] * n

  2. Calculating Degrees: The given list of roads is iterated over, and for each road [a, b], the degree of city a and city b is incremented by 1 since the road is bidirectional and connects both cities.

    1for a, b in roads:
2    deg[a] += 1
3    deg[b] += 1

  3. Sorting: The deg list is sorted in non-decreasing order. This ensures that cities with higher degrees, which should receive higher values, are at the end of the list.

    1deg.sort()

  4. Assigning Values: An enumerate loop is used, starting from 1, to calculate the sum of the products of the indices and the corresponding degrees. The index i effectively represents the value to be assigned to the city (as per sorted degrees), and v represents the degree of that city.

    1return sum(i * v for i, v in enumerate(deg, 1))

    Since the degree array is sorted, the city with the lowest degree is given the value 1, the next one is given 2, and so on, until the city with the highest degree is given the value n.

This approach guarantees that the sum of the road importances is maximized because it assigns the highest values to the cities with the highest degrees. The sorting step is essential to accomplish this allocation efficiently; otherwise, we would have to manually choose the highest values for the cities with the most roads.

Computational Complexity:

  • The computational complexity of counting the degrees is O(E), where E is the number of roads since we loop through each road only once.
  • Sorting the deg list takes O(N log N) time, where N is the number of cities.
  • The final enumeration and sum take O(N) time.

Hence, the overall time complexity of the solution is dominated by the sorting step, making it O(N log N). The space complexity is O(N) due to the extra deg list used to store the degrees.

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

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example Walkthrough

Assume we have n = 4 cities and the following list of bidirectional roads: roads = [[0, 1], [0, 2], [0, 3], [1, 2]]. Our task is to assign integer values to these cities to maximize the total importance of the roads where the importance of each road is the sum of the values of the cities it connects.

  1. Initialization: We start by initializing a list deg to store the degree (number of roads connected) for each of the 4 cities.

    1deg = [0] * 4  # [0, 0, 0, 0]

  2. Calculating Degrees: For each road, increment the degree of both cities involved in the road by 1.

    1# roads = [[0, 1], [0, 2], [0, 3], [1, 2]]
2deg[0] += 1  # For road [0, 1]
3deg[1] += 1
4deg[0] += 1  # For road [0, 2]
5deg[2] += 1
6deg[0] += 1  # For road [0, 3]
7deg[3] += 1
8deg[1] += 1  # For road [1, 2]
9deg[2] += 1
10# Now deg = [3, 2, 2, 1]

  3. Sorting: Sort the deg list in non-decreasing order.

    1deg.sort()  # [1, 2, 2, 3]

  4. Assigning Values: Assign values from 1 to n following the sorted order of degrees and calculate the total importance.

    1# Using enumerate starting from 1, assign values and calculate total importance
2total_importance = sum(i * v for i, v in enumerate(deg, 1))
3# total_importance = 1*1 + 2*2 + 3*2 + 4*3 = 1 + 4 + 6 + 12 = 23

The total importance of all roads with this assignment is 23, which is the maximum we can achieve. To see if it's the best assignment:

  • City 0 has the highest degree, 3, so it gets the highest value, 4.
  • Cities 1 and 2 each have a degree of 2, so they get the next highest values, 3 and 2.
  • City 3 has the lowest degree, 1, thus it gets the lowest value, 1.

The sum of the importances for the roads is:

  • For road [0, 1]: 4 (city 0) + 3 (city 1) = 7
  • For road [0, 2]: 4 (city 0) + 2 (city 2) = 6
  • For road [0, 3]: 4 (city 0) + 1 (city 3) = 5
  • For road [1, 2]: 3 (city 1) + 2 (city 2) = 5

Add these up for a total importance of 7 + 6 + 5 + 5 = 23.

By following the solution approach, we've maximized the total importance by giving the cities with more connections higher values, and this example demonstrates that the total sum of the importance is indeed optimized.

Solution Implementation

1class Solution:
2    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
3        # Initialize a list to store the degree of each city.
4        # Degree means the number of direct connections to other cities
5        city_degrees = [0] * n
6      
7        # Calculate the degree for each city by iterating over each road
8        for road in roads:
9            # Increment the degree for both cities in the road connection
10            city_degrees[road[0]] += 1
11            city_degrees[road[1]] += 1
12      
13        # Sort the degrees in ascending order so that the city with the highest
14        # degree gets the highest importance value
15        city_degrees.sort()
16      
17        # Compute the total importance score
18        # Importance is calculated by multiplying each city's degree by its 
19        # importance rank which is determined by its position in the sorted list
20        total_importance = sum(importance * degree for importance, degree in enumerate(city_degrees, 1))
21      
22        return total_importance
23
1class Solution {
2  
3    // Function to calculate the maximum importance of the city network
4    public long maximumImportance(int n, int[][] roads) {
5        // Array to store the degree (number of roads) of each city
6        int[] degree = new int[n];
7      
8        // Increment the degree for both cities involved in each road
9        for (int[] road : roads) {
10            ++degree[road[0]];
11            ++degree[road[1]];
12        }
13      
14        // Sort the array to process cities with smaller degrees first
15        Arrays.sort(degree);
16      
17        // Initialize answer to calculate the sum of importances
18        long answer = 0;
19      
20        // Assign importance values to cities. The importance starts from 1 and goes up to n.
21        // The cities with the smallest degrees get the smallest importance values.
22        for (int i = 0; i < n; ++i) {
23            // Calculate importance for current city and add it to the answer.
24            // Importance is calculated by multiplying the city's degree with its importance value.
25            answer += (long) (i + 1) * degree[i];
26        }
27      
28        // Return the total importance for all cities
29        return answer;
30    }
31}
32
1#include <vector> // Include the vector header for using vectors
2#include <algorithm> // Include the algorithm header for sorting
3
4class Solution {
5public:
6    // Calculates the maximum importance of the cities based on the roads
7    long long maximumImportance(int n, vector<vector<int>>& roads) {
8        // Create a vector to store the degree (number of roads) for each city
9        vector<int> degreeCounts(n, 0);
10
11        // Iterate through each road to increment the degree of the two cities connected by the road
12        for (const auto& road : roads) {
13            ++degreeCounts[road[0]];
14            ++degreeCounts[road[1]];
15        }
16
17        // Sort the degree counts in non-decreasing order
18        sort(degreeCounts.begin(), degreeCounts.end());
19
20        // Initialize a variable to store the maximum importance sum
21        long long maxImportance = 0;
22
23        // Assign the importance to each city based on its degree count
24        // The city with the smallest degree gets an importance of 1, the next one gets 2, and so on
25        for (int i = 0; i < n; ++i) {
26            maxImportance += static_cast<long long>(i + 1) * degreeCounts[i];
27        }
28
29        // Return the calculated maximum importance sum
30        return maxImportance;
31    }
32};
33
1// Importing the `Sort` from array helper functions to use sorting
2import { Sort } from "./arrayHelpers";
3
4// Function to calculate the maximum importance of the cities based on the roads
5function maximumImportance(n: number, roads: number[][]): number {
6    // Create an array to store the number of roads connecting to each city
7    let degreeCounts: number[] = new Array(n).fill(0);
8
9    // Iterate through each road to increment the road count for the connected cities
10    roads.forEach(road => {
11        degreeCounts[road[0]]++;
12        degreeCounts[road[1]]++;
13    });
14
15    // Sort the degree counts in non-decreasing order
16    degreeCounts.sort((a, b) => a - b);
17
18    // Initialize a variable to store the maximum importance sum
19    let maxImportance: number = 0;
20
21    // Assign importance to each city based on its road count
22    // The city with the smallest number of connecting roads gets an importance of 1, the next one gets 2, and so on
23    for (let i = 0; i < n; i++) {
24        maxImportance += (i + 1) * degreeCounts[i];
25    }
26
27    // Return the calculated maximum importance sum
28    return maxImportance;
29}
30
31// Note: The above code assumes the existence of a 'Sort' method for sorting arrays, which is not a built-in function in TypeScript.
32// A sorting function would need to be implemented or imported from a utility library for the sorting to work correctly.
33```
34
35In TypeScript, there's no native `Sort` method as it's written in the comment, because TypeScript leverages the JavaScript array `sort` method directly. The import at the top is demonstrating the structure but isn't needed for native JavaScript/TypeScript `sort` method. Here's the correct implementation without an import:
36
37```typescript
38// Function to calculate the maximum importance of the cities based on the roads
39function maximumImportance(n: number, roads: number[][]): number {
40    let degreeCounts: number[] = new Array(n).fill(0);
41
42    roads.forEach(road => {
43        degreeCounts[road[0]]++;
44        degreeCounts[road[1]]++;
45    });
46
47    degreeCounts.sort((a, b) => a - b);
48
49    let maxImportance: number = 0;
50
51    for (let i = 0; i < n; i++) {
52        maxImportance += (i + 1) * degreeCounts[i];
53    }
54
55    return maxImportance;
56}
57
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following problems can be solved with backtracking (select multiple)

Time and Space Complexity

Time Complexity:

The time complexity of the code consists of the following parts:

  • Initializing the degree list deg with n zeros has a time complexity of O(n).

  • Iterating over the list of roads to calculate the degree for each node: As there is one iteration over the list of roads, where the list's length is the number of roads r, this part has a time complexity of O(r).

  • Sorting the deg list: The sorting operation has a time complexity of O(n log n), as Python uses TimSort (a hybrid sorting algorithm derived from merge sort and insertion sort) for sorting lists.

  • The list comprehension with enumerate to compute the sum of importance: This iteration is done over the n elements of the sorted deg list, so its time complexity is O(n).

The overall time complexity is determined by the largest of these, which is O(n log n) due to the sorting operation. Thus, the total time complexity is O(n log n).

Space Complexity:

The space complexity of the code includes:

  • The deg list, which consumes O(n) space.

  • The internal space required for sorting, which in Pythonโ€™s sort implementation can be O(n).

  • The space required for the list in list comprehension when enumerate is called. However, since there's no separate list being created and it is an iterator, it does not add to the space complexity.

Considering all the above, the overall space complexity of the function is O(n). This is because, while there is temporary space used during sorting, the main permanent space used is the deg array which is linear in size to the number of nodes n.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ