🎨Now live: Try our Free AI Image Generation Feature

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
- 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.
- 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.
- 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 citya
and cityb
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
infreq
, increment the count of cities with frequencyx
in thecnt
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 indexidx
, assign the current valuecur
tox
cities, where each assignment increasescur
by 1. - Add the product of
idx
(the frequency) andcur
tores
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;
};