Maximum Total Importance of Roads | Thought Process | Leetcode 2285 | codestorywithMIK
Vložit
- čas přidán 26. 06. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 50th Video of our Playlist "Graphs : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good observation practice problem : Maximum Total Importance of Roads | Thought Process | Leetcode 2285 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Maximum Total Importance of Roads | Thought Process | Leetcode 2285 | codestorywithMIK
Company Tags : ADOBE
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/maximum...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
The approach to solving the problem of calculating the maximum importance of nodes in a graph involves the following steps:
Degree Calculation:
Initialize an array to store the degree (number of edges connected) of each node.
Traverse the list of roads (edges) to update the degree of each node.
Sorting:
Sort the degree array in ascending order. This allows assigning higher values to nodes with higher degrees in the subsequent step.
Calculating Maximum Importance:
Initialize variables to track the current value and the total sum.
Iterate over the sorted degree array, multiplying each degree by an incrementing value, and add the result to the sum.
Result:
The final sum represents the maximum importance, calculated by strategically assigning higher values to nodes with higher degrees.
By sorting the degrees and assigning incremental values, the approach ensures that nodes with higher connectivity contribute more to the overall importance, thus maximizing the total importance.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
MIK, really you are gem. I felt happy that mujhe apka channel mila. From long time, I did not do DSA, hence I followed your channel, which actually hit the mark ki beginner kaise sochega. I have been following your channel from last 5-6 months and really abhi intuition build hone laga hai.
I actually solved this question on my own using Map and PriorityQueue, I came to see optimised thought.
I actually recommend your channel to my friends, really helped me lot.
Please don't stop teaching and intuition build krna and story ce code krna, is actually a plus for this channel because har koi leetcode contest ke level ka person nahi hota...
Awesome....🙂
Made my day 🙏❤️🙏
@@codestorywithMIK Yes sir thanks a lot for your diligent efforts in making us understand dsa concepts easily!
Amazing
I just solved it using map twice,and in a very legthy method.....But your approach gave me the twist and eye of observation...thanks mik...
I have been watching your videos from 3 months and your explanations are too good just wanted to say thank you. Keep coming with more and more content every day
Solved it before just came here to thank you sir. Your story to code approach helped me improve so much 🛐🙏🏻
I have been watching your video when your subscribers 5k and your explanation is very good 😊 . Thank you so much 🙏.
Hey mik a small request please complete the dp concept and questions playlist We all wanna learn how to solve the game theory questions
Why? Pehle segment tree krna chahiye
@@xiaoshen194 bhaii syd tumhe thode din hi huye haii subscribe kiyee jo bhi purane subscribers hai they all know dp concepts and questions vaala playlist pichle 1 saal se pending padha haii toh but obvious phle vo complete hoga na but theeke we believe in mik vo krlegaa😍
Bhaiyia ek video bna dijiye jisame constraint dekh kar pata kar ki konsi time complexity ka solution work kar jayega isame.
thank you so much bro
I have not studied graph but I was able to solve both questions with logic (LeetCode POTD 27 & 28 June)
Hello mik,
I like your code story❤
Thank you!
Radiate positivity and attract greatness! 💫
Maine heap se banaya. But ye approach mast tha yaar
I solved on my own, took some time
you are the best man. I have learned so much from you in last few weeks than any other resource. thanks a lot for making this channel
Me nodding 🤭when you say "Tum smj rhe ho na ma kya kehna chah rha hu"
are bhai same 😂😂😂
same here brother 😊
your explanation is masterpiece ...that's why i love to do leetcode POTD ....
Thanks a lot bhaiya ❤❤ congrats for 54ksubs 🥳🥳
alraedy solved on own in single attempt, still here for your thought process
Did in my own. Support++❤
I have a humble request can you please make a video on recent weekly contest question no 3.
Bhaiya *palindrome substring* ka aapne *blue print* diya tha uske *variant* karwaiye please
Bhaiya, please Leetcode 2035 par video bana do plzz...🙏🙏🙏 I request you bhaiya...
when will youu start concept playlists, dp is incomplete.
Bro counting sort is optimial in this case...
bhaiya here 8:48 , the sum is 33 not 35 , rest is good
8:21. sum is 33
right bro sum is 33 not 35 @codestorywithMIK
|| JAVA SOLUTION ||
class Solution {
public long maximumImportance(int n, int[][] roads) {
long[] degCnt = new long[n];
long res = 0;
for(int[] road : roads){
degCnt[road[0]]++;
degCnt[road[1]]++;
}
Arrays.sort(degCnt);
for(int i=0; i
My Solution using Priority Queue(MaxHeap):
class Solution {
public:
long long maximumImportance(int n, vector& roads) {
vector degree(n, 0);
// Count the degree of each vertex
for (const auto& road : roads) {
degree[road[0]]++;
degree[road[1]]++;
}
priority_queue pq;
for(int i=0;i
start dp
hello sir, I wrote the code differently is their any issue in the code....
long long maximumImportance(int n, vector &roads)
{
unordered_map mp;
for (auto &vec : roads)
{
int a = vec[0];
int b = vec[1];
mp[a]++;
mp[b]++;
}
vector vec(mp.begin(), mp.end());
sort(vec.begin(), vec.end(), [](const pair &a, const pair &b)
{ return a.second > b.second; });
long long ans = 0;
long long i = n;
for (auto it : vec)
{
ans += it.second * i;
i--;
}
return ans;
}
Sahi hai bhai
public long maximumImportance(int n,int[][]roads){
int[]degree =new int[n];
for(int[]road:roads){
degree[road[0]]++;
degree[road[1]]++;
}
int[]cnt=new int[n];
for(int b:degree){
cnt[b]++;
}
long sum=0,value=1;
for(int i=0;i
only watching till 11:00
I got some idea
and was able to solve on my own ( had to use chatgpt for some syntax issues)
class Solution {
public long maximumImportance(int n, int[][] roads) {
HashMap freq = new HashMap();
for(int[] road:roads){
int u = road[0];
int v = road[1];
freq.put(u, freq.getOrDefault(u,0)+1);
freq.put(v, freq.getOrDefault(v,0)+1);
}
TreeMap sorted = new TreeMap((a, b) -> {
int freqCompare = Integer.compare(freq.get(b), freq.get(a)); // Sort by frequency (descending)
return (freqCompare != 0) ? freqCompare : Integer.compare(a, b); // Sort by key (ascending) for tie-breaking
});
sorted.putAll(freq);
int[] cityValues = new int[n];
int val = n;
for(Map.Entry pair:sorted.entrySet()){
int key = (int)pair.getKey();
int value = (int)pair.getValue();
cityValues[key] = val;
val--;
}
long ans=0;
for(int[] road:roads){
int u = road[0];
int v = road[1];
ans += cityValues[u];
ans += cityValues[v];
}
System.out.println(Arrays.toString(cityValues));
return ans;
}
}