2285. Maximum Total Importance of Roads | Greedy | Indegree OutDegree | Graph

In this video, I'll talk about how to solve Leetcode 2285. Maximum Total Importance of Roads | Greedy | Indegree OutDegree | Graph
Let's Connect:
📱Discord (Join Community) : / discord
📝Linkedin: / aryan-mittal-0077
📸 Instagram: / codewitharyanbhai
💻 Twitter - / aryan_mittal007
🤖 Github: github.com/ary...
About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)
✨ Timelines✨
✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

[@ARYANMITTAL]

Master Leetcode in 2024 - th-cam.com/video/ZbkG8-ifnIk/w-d-xo.html

[@vickyroy3595]

finally solved by myself , still watching your videooo!

[@ARYANMITTAL]

🫡🫡orzz🫡🫡

[@manishgaming4638]

Easy q , solved on my own, took some time to get intuition

[@RohitKumar-hn6wj]

🙏🙏🙏🙌🙌

[@Reckon-no2qv]

Java Solution Easy:
public long maximumImportance(int n, int[][] roads) {
long deg[] = new long[n];
for(int x[]:roads){
deg[x[0]]++;
deg[x[1]]++;
}
Arrays.sort(deg);
long sum=0;
long val=1;
for(long it:deg){
sum+= it*val;
val++;
}
return sum;
}

[@Samtoosoon]

Why used long long?

[@vijayanks1714]

Nice explanation if would add Time complexity explanation it too great bcz Leetcode editoria say it is O(n^2) but how it is possible?

[@ARYANMITTAL]

Ohh yeah sorry forgot to discuss that, it is O(nlogn), don’t believe leectcode🌚🤌🏻

[@shikharjoshi2998]

priority_queue tag has also been mentioned on leetcode , how to do from that? i myself came up with the solution that u are telling here but i am just curious that how priority_queue will help here ?

[@AB-cc4km]

class Solution {
public:
long long maximumImportance(int n, vector& roads) {
unordered_mapmp;
for(auto it:roads)
{
mp[it[0]]++;
mp[it[1]]++;
}
priority_queuepq;
for(auto it:mp)
{
pq.push({it.second,it.first});
}
long long i = n;
unordered_mapmp2;
while(!pq.empty())
{
long long x = pq.top().second;
pq.pop();
mp2[x] = i;
i--;
}
long long ans = 0;
for(auto it:roads)
{
ans+=(mp2[it[0]]+mp2[it[1]]);
}
return ans;
}
};

[@rishabhranjan5162]

@@AB-cc4km thanks, I was having trouble assigning valuse after getting the degrees, guess priority queue was the most efficient.