Maximal Network Rank | Simple and Straight | 2 Ways | MICROSOFT | Leetcode-239 | Dry Run | Live Code

[@ShivangiBansal-e8x]

Hey MIK, thanks for creating such a relevant content on DP. I could finally have a grasp on DP and convert the code from recursion to memoization. Thanks to your. Channel I was able to crack Google coding rounds.

[@codestorywithMIK]

Google Coding rounds. Woww ❤️💪💪 Congratulations on this achievement And thank you for your kind words ❤️❤️

[@thekindspill]

Wow

[@AlishaKhan-ww3io]

Wow. congrats

[@anuppatankar4294]

Congratulations 👌🏻

[@gp7060]

Was able to write code after listening your question explanation . Awesome explanation❤

[@GeniusOG]

I have done this by my own after understanding problem from your video, Thanks for the another great video. 😊

[@codestorywithMIK]

Thank you 😊

[@iamnoob7593]

Thank you , Understood. Very well explained

[@Raj10185]

Thank you so much understand everything

[@shikharpandya4927]

Thanks a lot Did it on my own. mission complete graph playlist + dp playlist 😇

[@ce019vivek5]

Great Explaination 👍

[@codestorywithMIK]

iPad PDF Notes - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-1615-Maximal%20Network%20Rank.pdf **************** JAVA CODE ************** class Solution { public int maximalNetworkRank(int n, int[][] roads) { Map adj = new HashMap(); for (int[] road : roads) { adj.computeIfAbsent(road[0], k -> new HashSet()).add(road[1]); adj.computeIfAbsent(road[1], k -> new HashSet()).add(road[0]); } int maxRank = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int i_rank = adj.getOrDefault(i, Collections.emptySet()).size(); int j_rank = adj.getOrDefault(j, Collections.emptySet()).size(); int rank = i_rank + j_rank; if (adj.getOrDefault(i, Collections.emptySet()).contains(j)) { rank--; } maxRank = Math.max(maxRank, rank); } } return maxRank; } }

[@wearevacationuncoverers]

Thank you for listening to our requests for adding PDF as well. ❣❣

[@thekindspill]

thanks

[@anuppatankar4294]

Great Video 😍

[@codestorywithMIK]

Thank you 😊

[@JoyAcharyatvl]

Thanks vai, It was awesome. Thanks again.

[@codestorywithMIK]

Thank you 🙏 😇

[@NITianMonika]

Your explanations in very good

[@codestorywithMIK]

Thanks a lot

[@umeshbisht1054]

Thanku bhaiya ❤

[@harikrushnasuhagiya3925]

Thanks a lot man.

[@AmarjeetKumar-to9ub]

Thank You :)

[@sauravbiswajit8091]

Thanksss a lot sir

[@codestorywithMIK]

Most welcome 😇

[@floatingpoint7629]

thanks for the super explanation. the question was confusing and difficult to understand specially why the -1, but you made it easy.

[@codestorywithMIK]

Thank you 😊

[@vaibhavgupta973]

thank you

[@codestorywithMIK]

You're welcome😇

[@kashishkashyap6229]

I was able to solve it myself since I have watched your complete graph concepts Playlist.

[@codestorywithMIK]

Awesome ❤️😇

[@manasdeora4601]

Very beautifully explained. Thanks bro

[@codestorywithMIK]

Thank you so much ❤️❤️

[@rabeakhatun2819]

Nice dada , another similar problem on this is on triplets in leetcode

[@codestorywithMIK]

Thank you 😊

[@oqant0424]

i am happy that i was able to solve it on myself (though i did some mistakes but after watching only few minutes i realised where i was wrong and then corrected them and it passed).............thanks for teaching us ki sawal karte kaise karte hain

[@codestorywithMIK]

Awesome Thank you ❤️😇

[@YashSinghal]

what makes your videos best is you never assume that the viewer knows it already, you even explain the question with time and patience ❤

[@codestorywithMIK]

Thanks a lot Yash 😇🙏

[@unknown47896]

my basic observation approach by degrees class Solution { public: int maximalNetworkRank(int n, vector& roads) { unordered_map adj; vector degree(n,0); for(auto it: roads) { adj[it[0]].push_back(it[1]); adj[it[1]].push_back(it[0]); degree[it[0]]++; degree[it[1]]++; } int maxi=INT_MIN; for(int i=0;i

[@xiaoshen194]

I was also thinking about indegree-ish kind of algo. Good explanation. Thnx 👍

[@keertilata20]

same

[@souvikmukherjee8245]

At first, this question seemed daunting 😳, but your explanation made it appear much simpler 😌.

[@codestorywithMIK]

Glad it was helpful! ❤️😇🙏

[@NeerajKumar-cj6ky]

Your video is fantastic but i want to request that please tell the time complexity in little more brief and also space complexity.

[@codestorywithMIK]

Sure thing ❤️❤️❤️

[@__VishalSharma]

Bhai thank you for these videoes pls also start the weekly contest post discussion on the channel.

[@AlishaKhan-ww3io]

Thanks a lot

[@ugcwithaddi]

Legend

[@neelx9437]

Bhaiya in the description its written 32nd video of sliding window playlist instead of graphs. Again thanks bhaiya for maintaining my consistency❤❤. Here's my java code- class Solution { public int maximalNetworkRank(int n, int[][] roads) { int maxRank = 0; List adj=new ArrayList(); for(int i=0;i

[@codestorywithMIK]

Wow. Thanks a lot for mentioning. Corrected ❤️❤️

[@sauravchandra10]

Surprisingly brute force wala code accept hogya

[@codeandtalk6]

❤❤

[@thekindspill]

You made it look so easy

[@abhishekverma7604]

isko kahns algorithm se bhi kar skte hn,like creating indegree array and then performing plain bfs..

[@shahchandan8208]

Sir please also upload the graph concept lecture IPad notes . Bahut jada help ho jaega sir.

[@souravjoshi2293]

Thanks a lot man. Crystal clear

[@aswithasai4015]

But there will be log n complexity for insertion in set right

[@codestorywithMIK]

The insert operation in unordered_set in C++ has Average Time complexity of O(1) en.cppreference.com/w/cpp/container/unordered_set ❤️❤️

[@aswithasai4015]

@@codestorywithMIK ohh ok thank you

[@taneyasoni]

18/31 #augustchallengewithMIK

[@kamalkothari4843]

will the road numbers be 0,1,2,3,... or it can be random 2,5,7, etc

[@kamalkothari4843]

and how to solve if road number is random

[@xiaoshen194]

​@@kamalkothari4843adj list se

[@souravjoshi2293]

It's mentioned in the constraint 0

[@thekindspill]

use adjacency list then

[@codestorywithMIK]

Yes, In that case we will have to use adjacency list of (int, vector)

[@santhosh7042]

i taught it can be solved by floyd warshall 😅

[@dayashankarlakhotia4943]

class solution { Public int maximal Network Rank(int n,int [][]roads){ list []graph =new Array list (); for (int i=0; i

[@jayendraawasthi2646]

using your second approach i tried doing the question in O(n) time complexity by just getting the maximum and second maximum values in degree array. It is working for almost 80+ test cases but fails in a very big test case. Can anyone tell me where i'm going wrong please. CODE: class Solution { public: int maximalNetworkRank(int n, vector& roads) { vector arr(n, 0); vector mat(n, vector(n, false)); for(auto road: roads){ int e1 = road[0]; int e2 = road[1]; arr[e1]++; arr[e2]++; mat[e1][e2] = true; mat[e2][e1] = true; } int maxi=0, secMaxi=-1; int res = INT_MIN; for(int i=1; i= arr[maxi]){ secMaxi = maxi; maxi = i; } else { if(secMaxi == -1){ secMaxi = i; } else if(arr[i] >= arr[secMaxi]) { secMaxi = i; } } int rank = arr[maxi] + arr[secMaxi]; if(mat[maxi][secMaxi]) rank--; res = max(res, rank); } return res; } };

[@codestorywithMIK]

Yeah actually this will not pass all test cases

[@AnandKumar-kz3ls]

i also tried to do this in O(N) but then realize if its a complete graph then there will be (n*(n-1)/2) edges which is eventually O(n^2)

[@priyanshusingh3316]

chalo graph se darr thoda kam ho gaya hai

[@codestorywithMIK]

So glad to know ❤️😇

[@keertilata20]

i was stuck on how to find if two cities are connected to each other or not

[@thekindspill]

Same. But got it cleared in starting minutes of the video and got it done myself

[@manaskhare412]

Great video, but I would like to point out the mistake that you have made in your 1st code, if(adj[i].find(j) != adj[i].end()) { total--; } which is this line, it's nothing to do with finding common roads, and it's surprising how your code got accepted 😂, All confused folks, use this code, and get your confusion clear 👇 if(adj[i].find(j) != adj[i].end()) { if(adj[j].find(i) != adj[j].end()) { total--; } }

[@codestorywithMIK]

Hi Manas , Sorry I didn’t get your code. Can you please elaborate a little ? adj[i].find(j) itself checks if i and j are connected (and since it’s bidirectional, we don’t have to check j to i)

[@ugcwithaddi]

Bhai , it’s an un directed graph 😅. No need to check for both condition. 😅

[@souravjoshi2293]

If i is connected to j, then there is no need to check for (j to i) bro. Both checks are not required.