2285. Maximum Total Importance of Roads

Intuition

The problem involves assigning values to cities such that the total importance of all roads is maximized. The importance of a road is the sum of the values of the cities it connects. To maximize the total importance, we should assign the highest values to the cities that appear most frequently in the roads array. This is because the importance of each road increases with the values of the cities it connects.

Approach

1. Calculate Frequencies: - Create a frequency array to count the number of roads connected to each city. - Traverse through the roads array and increment the counts for the connected cities.
2. Sort Frequencies using Counting Sort: - Use counting sort to sort cities based on their frequencies. This is more efficient than a general-purpose sort when the range of frequency values is small compared to the number of cities.
3. Assign Values Optimally: - Assign the highest available values to the cities with the highest frequencies. - Calculate the total importance by summing the importance of each road using the assigned values.

Complexity

• Time Complexity: - Calculating the frequencies takes O(n) time, where n is the nnumber of cities. - Counting sort takes O(n) time. - Assigning values and calculating the total importance takes O(n) time. - Overall time complexity is O(n).
• Space Complexity: - Additional space is used for frequency arrays and counting sort, which is O(n). - Overall space complexity is O(n).

Code Explanation

1. Initialize Arrays and Variables

var freq = new Uint32Array(n);
var cnt = new Uint32Array(n);
var res = 0;
var cur = 1;

• freq is an array initialized with zeros, used to count the number of roads connected to each city.
• cnt is an array initialized with zeros, used to count the number of cities with each frequency.
• res is a variable to store the result (the maximum total importance).
• cur is a variable to keep track of the current value being assigned to a city.

2. Count the Frequency of Each City

roads.forEach(([a, b]) => { 
    ++freq[a], ++freq[b] 
});

• Iterate over each road in the roads array.
• For each road [a, b], increment the frequency of city a and city b by 1.

3. Count the Number of Cities with Each Frequency

freq.forEach((x) => ++cnt[x]);

• Iterate over the freq array.
• For each frequency x in freq, increment the count of cities with frequency x in the cnt array.

4. Assign Values to Cities Based on Their Frequencies

cnt.forEach((x, idx) => { 
    while (x--)
        res += idx * cur++ 
});

• Iterate over the cnt array.
• For each count x at index idx, assign the current value cur to x cities, where each assignment increases cur by 1.
• Add the product of idx (the frequency) and cur to res for each assignment.

5. Return the Maximum Total Importance

return res;

• Return the final calculated result res which represents the maximum total importance of all roads after assigning the values optimally.

Code

C++

class Solution {
public:
    long long maximumImportance(int n, vector>& roads) {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        vector freq(n, 0);
        vector cnt(n, 0);
        long long res = 0;
        long long cur = 1;

        for (const auto& road : roads) {
            ++freq[road[0]];
            ++freq[road[1]];
        }

        for (const auto& x : freq) {
            ++cnt[x];
        }

        for (long long idx = 0; idx < cnt.size(); ++idx) {
            for (int i = cnt[idx]; i > 0; --i) {
                res += idx * cur++;
            }
        }

        return res;
    }
};

Python

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        freq = [0] * n
        cnt = [0] * n
        res = 0
        cur = 1

        for road in roads:
            freq[road[0]] += 1
            freq[road[1]] += 1

        for x in freq:
            cnt[x] += 1

        for idx in range(len(cnt)):
            for _ in range(cnt[idx], 0, -1):
                res += idx * cur
                cur += 1

        return res

Java

class Solution {
    public long maximumImportance(int n, int[][] roads) {
        int[] freq = new int[n];
        int[] cnt = new int[n];
        long res = 0;
        long cur = 1;

        for (int[] road : roads) {
            freq[road[0]]++;
            freq[road[1]]++;
        }

        for (int x : freq) {
            cnt[x]++;
        }

        for (int idx = 0; idx < cnt.length; ++idx) {
            for (int i = cnt[idx]; i > 0; --i) {
                res += idx * cur++;
            }
        }

        return res;
    }
}

JavaScript

/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var maximumImportance = function (n, roads) {
    var freq = new Uint32Array(n);
    var cnt = new Uint32Array(n);
    var res = 0;
    var cur = 1;

    roads.forEach(([a, b]) => { ++freq[a], ++freq[b] });
    freq.forEach((x) => ++cnt[x]);
    cnt.forEach((x, idx) => { while(x--) res += idx * cur++ });

    return res;
};