Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python

[@jamesnguyen3459]

Stuck with this for today challenge. Thank you for a detail explanation

[@keshavgoswami9846]

I solved the question without seeing any solution and with your idea until 6:10 of the video. Thanks for the great explanation.

[@MP-ny3ep]

Thank you , this solution seems so easy when you code it up.

[@vishalplayzz2580]

c++ code for those who are struggling class Solution { public: long long result=0; int dfs(int node,int parent,unordered_map&adj,int seats) { int passengers=0; for(auto &x:adj[node]) { if(x!=parent) { int p=dfs(x,node,adj,seats); passengers+=p; result+=(int)ceil(p*1.0/seats); } } return passengers+1; } long long minimumFuelCost(vector& roads, int seats) { unordered_mapadj; for(auto &x:roads) { adj[x[0]].push_back(x[1]); adj[x[1]].push_back(x[0]); } dfs(0,-1,adj,seats); return result; } };

[@PujaKumari-zl7rw]

Hi, Can you tell me why do we need (p*1.0/seats) above?

[@laumatthew71]

​ @Puja Kumari In case we simply use (p / seats), C++ will perform integral division (divide and round down) and return a rounded down integer (which will lead to a wrong answer). p * 1.0 will result in a double type and further divide it will give us the correct result. Hope this help !

[@vishalplayzz2580]

@@PujaKumari-zl7rw wo example dekho like usme at node 2 we have passengers=3 to be moved from node 2 to 0 and har car me 2 seat hai we have 3 nodes to be moved so we need 2 cars right so we use ceil(p/seats ) and 1.0 for floating value to convert into int value since ceil deals with floating values if we do direct 3/2 here ans is 1 right so 3*1.0/2 lagane se we get ceil(1.5)=2

[@Tim_desu]

So clear and concise, thx dude

[@CostaKazistov]

DFS solution is much nicer for this problem compared to BFS (which is doable but slightly harder to write)

[@mohithadiyal6083]

Just amazing explanation

[@krateskim4169]

Awesome explanation

[@AceAlgo]

Bro, I really wish you can fill all LC questions one day lol.

[@kwakukusi4094]

best explanation

[@devinpadron5]

7:50 shouldn't space complexity be O(N) since we are building an adjacency list?

[@Codisrocks]

I originally misread it to think that each car had a different capacity. That would have been an interesting problem.

[@akashdey5637]

why does the dfs call return the number of current passengers?

[@kewtomrao]

This was a really nice problem

[@rafaeldietrich8050]

That was fast!

[@mayurpande2433]

What if each city has car with variable seat basically we are given list of seats?

[@ratin754]

0:12 hmm🧐

[@NeetCodeIO]

😳

[@juliuskingsley6212]

XD

[@harshitpant07]

not cleared about something 1st: we are going from bottom to the root nodes right or from root to bottom 2nd: what's the use of passenger+1 , '+1' didn't understand

[@kumarspandanpattanayak3489]

we are going from root to bottom and passengers + 1 is needed to include the node itself to the passengers variable

[@ary_21]

Why a second channel when you could have posted this from your main account and add it to the existing graph playlist making it 1 stop solution for all neetcode graph problems ?

[@yang5843]

He wants to make non-Leetcode solution related content in the future for his main channel

[@NeetCodeIO]

I can still add these videos to the playlists on the main channel, I'll prob do that and then link the playlists in the video descriptions

[@anshumansinha5874]

I could not understand this, let's take the example at @7:26 , why is it 4 fuel to reach from node 2 to 0? can we not take a car which has 5 seats and take all the 3 people at node 2 so only 1 fuel from there onwards.