Maximum Total Importance of Roads - Leetcode 2285 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/maximum...
0:00 - Read the problem
0:30 - Drawing Explanation
7:53 - Coding Explanation
leetcode 2285
#neetcode #leetcode #python

[@CheeseDiablo]

You can apply bucket sort here to avoid sorting the array of edge counts which gives you linear time instead of O(nlogn)

[@akialter]

I think for large n the overhead of initiating dsa for bucket/count sort outweighs nlogn sorting algorithms. Good to mention in interview but implementation like this is good enough

[@IamAWESOME3980]

i seriously have no idea what this question is even asking. after watching this video, i still have no idea why the edge add up to a value of 6 in the first graph

[@maanas_sehgal]

See u have to assign values to the nodes just that u have a max sum so just assign values to the nodes and add them up. If u have a and b node connected, if a has value 4 (not the node val but the value u assign) and other has 2, ulso u add up 6

[@jadenschulz1004]

2 + 3 = 6 duh (i am also confused)

[@maanas_sehgal]

​@@jadenschulz1004 Not 2 plus 3, see nodes 0 and 1 and there u have values 2 and 4 which gives u 6. The problem is to find what u assign the values there, if u had a 3 instead of 4, u would have gotten 5

[@chandrur6941]

I thought the same, but the explanation given by Neetcode is misleading. Assume edges represent the number of routes. According to the example: Node 2 has 4 routes, Node 1 has 3 routes, Nodes 0 and 3 have 2 routes each, Node 4 has 1 route. To maximize total importance, assign the highest number to the node with the most routes: Node 2 => 5 Importance (assume importance as priority) Node 1 => 4 Importance Node 3 => 3 Importance (Node 3 can also come first, but the answer will not change) Node 0 => 2 Importance Node 4 => 1 Importance Now add the importance between edges and return the result. So to answer your question, if we add the edges in first graph, we will get 5 as a result, which is incorrect as per the explanation. We need to add the importance, which is 4 + 2 = 6.

[@rammohan2870]

This is the best explanation that i can ever get. Mind Blowing explanation. Bro i became a big fan.

[@yang5843]

Thanks for uploading this This was a good question, the question had two distinct components to it

[@addiegupta]

man you make every problem look so easy. respect

[@jamestwosheep]

I love this explanation, it's so simple. I totally overthought this problem by making an entire adjacency list in my first step.

[@maanas_sehgal]

Sameee but I was able to come up with the same solution but in java lol😅

[@freecourseplatformenglish2829]

I solved it on my own but find your solution a bit compact. Happy to learn a better way.

[@eshukla15]

I'll always be grateful for your videos, kindly keep uploading the daily problem solutions, we all will be grateful for that

[@arijaa.9315]

This time the eplanation is so contradict at the begining, I ffind it hard to understand how summing the number of edges for nodes 0 and 1 to be 6 hen 2+3 = 6 then your explanation changed into different idea. I see all your videos that is why I am writing

[@Antinormanisto]

I don't understand the question and even your explanation what I must do EDITED: I understood the question. I didn't understand where we take values for vertexes

[@Nishanth_S]

Learn basics and find another video in the same topic that you can understand

[@pineappl3pizzzasoju]

Same, I have done a few graph problem and am comfortable traversing dfs/bfs. But this problem in particular, I am having a hard time understanding what it wants.

[@abhishekkumar-fe8lw]

@@pineappl3pizzzasoju You need to assign the greatest value to the most important road to maximiize the sum. The most important road is the one which has been visited the most. Just find the degree of al the node,and sort it,the one with the highest degree is most important. Hope you understood it.

[@DebopriyoBasu]

You have a 2D array. But consider it as a 1D array. store the occurrence of a number using arr[0] and arr[1] for each subarray in a 1D array. That is the degree of a node. Now sort the degrees in ascending order. Then start a counter from 1 to the number of degrees and multiply the counter to the degree and keep on adding it to a sum. Return that sum as answer.

[@pineappl3pizzzasoju]

@@abhishekkumar-fe8lw Thank you, I was able to solve it after understanding that the key most important thing is to assign the greatest value to the city with most edges(roads) 🙏

[@MrSpeedFrk]

Why start out with the more complex case and just go with the simple ... and shorten the length of the tutorial Probably just me and no offense I also have a bit of OCD but it seems like many of these videos could be condensed quite a bit