G-40. Number of Ways to Arrive at Destination

[@takeUforward]

For leetcode, just change to long long, and 1e9 to 1e18. Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79

[@rushikeshpol5844]

Hey brother can you solve leetcode skiplist problem in Java

[@lakshya588]

Bhiya graph k kitne lecture ayenge total approximately

[@pkedit8873]

testcases are failed on leetcode why??

[@Failed5555]

Bhaiya is it the last video of this graph series??

[@takeUforward]

test cases failing because of large test cases, just have long long and 1e9 to 1e18

[@KUSHALLOYA]

16:46 "I get excited but that's how I teach" fr🙇‍♂🙇‍♂

[@doodlelord]

which campus bro

[@kushalloya4640]

@@doodlelordpilani

[@doodlelord]

@@kushalloya4640 nice I'm from Goa. 26 batch?

[@purushottam108]

@@doodlelord tiet '27

[@vardhankumar4762]

His excitement for problem solving shows why he became so successful in this field.

[@preetkatiyar969]

Nobody can beat you in teaching style . You r such a gem.

[@karantaori8797]

THIS GUYS IS ABSOLUTELY GENIUS. HE BREATHES CODING AND HE EXHALES TEACHING!!

[@shreyarawatvlogs6920]

cant believe when i started with my first lecture of graph series and here i am completing the 40th lecture. Honestly, i took the online coding ninjas course and initially learnt graph from there but your explanation is way better than theirs. Also, the ways you relate every question is awesome. Thank you for these lectures.

[@Mohit_Q]

heyy you are in which year ?

[@shreyarawatvlogs6920]

@@Mohit_Q 3rd year

[@sukhpreetsingh5200]

currently doing tree series just here to appreciate your hard work !!thanks a lot for this amazing content.

[@sahilagarwal7752]

so happy that I figured it by myself and didn't need to look the solution. Greatest playlist ever. Thank you, man! You are a great teacher. Understood.

[@sumerrawat6947]

*For leetcode* take *long long* everywhere in place of *int* as the test cases are too large and also take LONG_MAX in distance array in place of 1e9

[@kunalsabadra6802]

Still its giving me wrong answer for last test case

[@HarshalDev]

@@kunalsabadra6802 use my code for reference ``` class Solution { public: int countPaths(int n, vector& roads) { // find "NUMBER" OF SHORTEST PATHS int MOD = 1e9 +7; vector adjList[n+1]; for(int i = 0 ; i < roads.size() ; i++){ long long u = roads[i][0]; long long v = roads[i][1]; long long time = roads[i][2]; adjList[u].push_back({v, time}); adjList[v].push_back({u, time}); } // direct dijkstra lagao and lage haath "ways" found out kro vector ways(n,0); ways[0] = 1; vector dist(n, LLONG_MAX); dist[0] = 0; priority_queue pq; pq.push({0, 0}); // dist, node while(!pq.empty()){ auto front = pq.top(); pq.pop(); long long d = front[0]; long long currcity = front[1]; for(auto &next : adjList[currcity]){ long long nextcity = next[0]; long long edgeWt = next[1]; if( d + edgeWt < dist[nextcity]){ dist[nextcity] = d + edgeWt; pq.push({ d + edgeWt , nextcity}); ways[nextcity] = ways[currcity]%MOD; } else if(d + edgeWt == dist[nextcity]){ ways[nextcity] += (ways[currcity])%MOD; } } } return ways[n-1]%MOD; } }; ```

[@AmrendraKumar-jn5mq]

Thanks dude😊

[@shreyanshagrawal3115]

what to do in java? there isnt long long

[@chetanya_sharma]

thanks bro

[@kushagramishra3026]

"Understood" and energy was super amazing in this video 😁 .

[@Ununtag]

I was doing the same mistake which striver mentioned at 4:58. He took the mistake in the beginning of the video itself. Really the mentor who knows what he is teaching.

[@Nirajkumar-h3e3p]

For all those, whose 13th test case is failing in GFG, just change distance /weights to long and take the maximum value as Long.MAX_VALUE class Pair { int node; long distance; Pair(int node, long distance) { this.node = node; this.distance = distance; } } class Solution { static int countPaths(int n, List roads) { ArrayList adj = new ArrayList(); for(int i = 0; i < n;i++) { ArrayList temp = new ArrayList(); adj.add(temp); } int m = roads.size(); for(int i = 0; i < m;i++) { adj.get(roads.get(i).get(0)).add(new Pair(roads.get(i).get(1),roads.get(i).get(2))); adj.get(roads.get(i).get(1)).add(new Pair(roads.get(i).get(0), roads.get(i).get(2))); } PriorityQueue pq = new PriorityQueue((x,y) -> (int)(x.distance - y.distance)); pq.add(new Pair(0,0)); long[] dist = new long[n]; int[] ways = new int[n]; for(int i = 0; i < n;i++) { dist[i] = Long.MAX_VALUE; ways[i] = 0; } dist[0] = 0; ways[0] = 1; int mod = (int)(1e9 + 7); while(pq.size() != 0) { Pair ele = pq.peek(); pq.remove(); int node = ele.node; long distance = ele.distance; for(Pair pair:adj.get(node)) { int adjNode = pair.node; long adjDist = pair.distance; if(adjDist + distance < dist[adjNode]) { dist[adjNode] = adjDist + distance; ways[adjNode] = ways[node]; pq.add(new Pair(adjNode, adjDist + distance)); } else if(adjDist + distance == dist[adjNode]) { ways[adjNode] = (ways[adjNode] + ways[node]) % mod; } } } return ways[n-1] % mod; // Your code here } }

[@pranavjaju411]

Thanks man!

[@aarnasinghal5057]

thanks for the help

[@saurabhmaddheshiya9001]

thanks for help

[@amitbajpai6265]

before watching the solution i applied the optimized approach that you taught in word ladder 2. First i find the min distance using dijekstra, then count the ways by using dfs technique. it passes example test case but later give the TLE.

[@sonit9707]

TLE because in dfs you might visit each node repeatedly.

[@keertilata20]

The excitement and enthusiasm on your face while teaching is priceless

[@prashudeshmukh7902]

Just see his expressions when he tells the most important part of algorithm 😂 it gives the adrenaline rush . Amazing teaching sir .... Thank u so much

[@lucygaming9726]

Was able to solve it on my own thanks to DP-47 (# of Longest Increasing Subsequence). I was able to build the intuition from that.

[@bishalkundu7592]

Just completed the Tree series ❤️ its really asm ❤️ really appreciate ur hardwork to improve our coding skills ❤️ Please continue this striver . U r a inspiration for us ❤️ thnks a lot ❤️

[@amanbhadani8840]

This problem has already been solved by you in one of old live sessions, thanks for the nice explanation.

[@shubhamraj25]

For anyone getting error in LEETCODE version of the same problem in last testcases, you need to make some changes, like convert all int to long long and 1e9 to 1e18. The working AC code for leetcode is this :- int mod = (long long)(1e9+7); vector adj[n]; for(auto it:roads){ adj[it[0]].push_back({it[1],it[2]}); adj[it[1]].push_back({it[0],it[2]}); } priority_queue pq; vector dist(n,1e18); vector way(n,0); dist[0]=0; way[0] = 1; pq.push({0,0}); while(!pq.empty()){ long long int node = pq.top().second; long long int dis = pq.top().first; pq.pop(); for(auto itr: adj[node]){ long long int adjNode = itr.first; long long int d = itr.second; // below code is for the case when we are reaching for the first time with // that less distance if(d+dis < dist[adjNode]){ dist[adjNode]=d+dis; way[adjNode] = way[node]; pq.push({d+dis,adjNode}); } else if(d+dis == dist[adjNode]) way[adjNode] = (way[adjNode]+way[node])%mod; } } return way[n-1]%mod;

[@pranavchandrode7127]

in gfg also we get error at testcase 13 due to this problem

[@chitranshjawere4953]

This is more or less very similar to finding out the number of Longest Increasing Subsequences :) Great Callback ! It makes me genuinely happy to see how 2 so different topics namely Dijkstra's and DP can be very similar at times. Dijkstra's is indeed beautiful.

[@stith_pragya]

Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@manasranjanmahapatra3729]

Dry run was super Amazing💪. Understood!

[@120-venkataraghavareddyvar4]

Will normal queue work here instead of priority queue??

[@rohanyelpale3365]

Hi Striver, just one question, if u have reached a node again with minimum distance then how u can update the ways array? eg. we reached to node 5 with distance 4 and ways count is currently 2. Now, with some other path we reached to node 5 with distance 3. Now what will be the way count? bdw love your videos🥰😍

[@vamsimudaliar8643]

Ways will be set to 3. Since, in the first case as we are taking longer distance. The ways to reach that longer distance should also be ignored.

[@sonit9707]

@@prateekpandey7449 Yes.

[@sidarthroy815]

@prateek pandey didn't understand

[@sidarthroy815]

@@vamsimudaliar8643 didn't understand

[@DevPanchal-e1h]

Yes Same Question , I think in that case you have to set ways of node to ways of node of with minimum distance and Set dist. min

[@MonuKumar-ne1ux]

For GFG Test Case 13 take Arrays.fill(dis,Integer.MAX_VALUE) insted of Arrays.fill(dis,(int)1e9+7);

[@vishalarya3818]

but it is giving answer 2

[@vinayaksinghal]

class Solution { public: int countPaths(int n, vector& roads) { int m=roads[0].size(); vector adj[n]; /* for(int i=0;i=time+t && newnode!=n-1){ dist[newnode]=time+t; vec.push_back(newnode); pq.push({time+t,vec}); vec.pop_back(); } else if(dist[newnode]>=time+t && newnode==n-1){ dist[newnode]=time+t; vec.push_back(newnode); ans.push_back({time+t,vec}); vec.pop_back(); } } } if(dist[n-1]==INT_MAX){ return 0; } int mint=INT_MAX; for(int i=0;i

[@pulkitjain5159]

solved it myself, thanks for this

[@priyanshkumar17]

Excellent Dry Run !! Understood

[@sabarinath9471]

Understood , thankyou for making these videos 😇😇

[@kanikagyamlani]

The 13th test case on gfg is causing some issues with this question, can you please check that out? However, after inserting the code " if (dis>dist[node]) continue; " after popping out the top element in the queue, the code is working fine, no idea how lol, so it would be helpful if you could take a look into that as well :)

[@iloveuniverse143]

use LONG_MAX in dist vector ..

[@faheemuddinnaseem6942]

To pass all test cases put value of dist array =2e9 initially because there will be some test cases where its weight will be given as 10^9 so it that cases putting dist array initial value=2e9 make sense.

[@kanishkgoel5946]

Thank you

[@siddhantyadav450]

but why does it not work when we put it as INT_MAX?? shouldnt it work for INT_MAX as well if its working for 2e9. Im not getting this part (ik it works for 2e9 i just checked)

[@UECAshutoshKumar]

Thank you sir 🙏

[@cinime]

Understood! So amazing explanation as always, thank you very much!!

[@AdityaPratapSingh-ss8wg]

Can we solve using normal queue?

[@divyansh2212]

solved before watching video...thanks🙏

[@RitamSharmaBBB]

is this an example of DP problem because we are storing previous values which are used later ?

[@Rajat_maurya]

Waiting for next videos

[@sambhavagarwal5871]

UNDERSTOOD,GOD OF GRAPH (STRIVER) U GRAPH SERIES IS FANTASTIC ,SUPARB,DONT HAVE WORS

[@suryakiran2970]

Understood❤, Excellent Teaching

[@ShivamKendre-fc3su]

Very well explanation

[@AyushiPanday12]

understood😊😊 Thankyou bhaiya for making such amazing vdos.

[@sharathkumar8338]

Done with all the 40 videos. waiting for upcoming videos as well. It is highly recommended to revise these questions and try to solve it on our own once again right?? Can any one in the comment response please??

[@krishanpratap3286]

yes otherwise u will not remember what u have solved practice is the key here which year u in?

[@sharathkumar8338]

@@krishanpratap3286 no bro 24 year old working professional

[@pavannettam8968]

Really great explanation !!

[@6mahine_mein_google]

PS :- Not errorless at one go 😆😆 There was a typo in line 26 int node=it.secoond , jump to @22:59 . Keep up the good work

[@sanketchoudhury527]

Solid explanation🔥 kudos to you man!!!

[@chintaphaniramavaibhav3714]

probably the best question i have learned from striver bhaiya series🤩

[@adityajhunjhunwala9739]

Amazing Explanation bro🔥loved it❤

[@YATHARTHBHARDWAJ-y8m]

understood bhaiya thank you so much for this awesome content

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

If we are getting lesser distance for the specific node, then , before adding the new element ( dist, node) to the priority queue, wont we remove the older one from it by using treeset instead of priority queue???

[@ProbuddhaSingha-c7r]

Errorless code at one go is an emotion 🙂

[@rushidesai2836]

Thank you Jiraiya sensei!

[@AmardeepMittal-qi1kx]

Hey Striver, I have been following you for a while, really like the way you explain the intuition and solution. For this question I was wondering why can’t we just use a queue instead of priority queue ?

[@danushbasanaboyina1306]

Using queue , it is giving (tle) Time Limit Exceeded , which has to do many operations. But using priority queue it reduces some operations that needs to be performed

[@AdityaPratapSingh-ss8wg]

@@danushbasanaboyina1306 hi have you tried that queues solution ? Because it is giving WA and that's what @AmardeepMittal-qi1kx question is!!

[@danushbasanaboyina1306]

@@AdityaPratapSingh-ss8wg I have done using queue where the sample testcases are correct but on submission it is giving TLE (Time Limit Exceeded).so it is preferred to use priority queue which reduces much needed operations. Thus reduces the time.

[@AdityaPratapSingh-ss8wg]

@@danushbasanaboyina1306 could you share your answer if possible or code link.

[@kushjain1986]

Using a queue instead of a priority queue for this problem might not give the correct results because Dijkstra's algorithm relies on the property that the node with the smallest distance is processed first. This ensures that once a node is processed, the shortest path to that node is guaranteed to be found. Using a regular queue would essentially turn the algorithm into a Breadth-First Search (BFS), which is not suitable for graphs with weighted edges unless all weights are equal (i.e., in an unweighted graph). However, for a scenario where all edge weights are equal (typically 1), a BFS-based approach would work correctly.

[@devanshsingh2]

For people facing issues in Leetcode in Java :- Use long for time since test cases are too large // CODE :- class Pair { int node; long time; Pair (int node, long time) { this.node = node; this.time = time; } } class Solution { public int countPaths(int n, int[][] roads) { // 0 to n-1 // create adj list List adj = new ArrayList(); for (int i = 0; i < n; i++) adj.add(new ArrayList()); for (int[] road : roads) { int u = road[0], v = road[1]; long t = road[2]; adj.get(u).add(new Pair(v, t)); adj.get(v).add(new Pair(u, t)); } // Dijkstra on time PriorityQueue pq = new PriorityQueue((a, b) -> Long.compare(a.time, b.time)); long[] time = new long[n]; Arrays.fill(time, Long.MAX_VALUE); int[] ways = new int[n]; time[0] = 0; ways[0] = 1; // start node pq.offer(new Pair(0, 0)); int mod = (int)(1e9 + 7); while (!pq.isEmpty()) { Pair curr = pq.poll(); int u = curr.node; long tt = curr.time; // total time if (tt > time[u]) continue; // no use of checking neigs for (Pair neig : adj.get(u)) { int v = neig.node; long t = neig.time; if (tt + t < time[v]) { time[v] = tt + t; pq.offer(new Pair(v, tt + t)); ways[v] = ways[u]; // ** } else if (tt + t == time[v]) { // ** ways[v] = (ways[v] + ways[u]) % mod; } } } return ways[n - 1]; } }

[@parthkandwal8343]

Another brilliant video Sir

[@sangeetasharma8574]

loved the energy!!

[@ishangujarathi10]

loveddd your intuition and logic

[@amritkumar2381]

// Leetcode all test cases passed // Instead of storing int in dist vector we can store pair to store {min distance, ways} int countPaths(int n, vector& roads) { int mod=1e9+7; vectoradj[n]; for(auto it : roads) { adj[it[0]].push_back({it[1], it[2]}); adj[it[1]].push_back({it[0], it[2]}); } vectordist(n, {1e18, 0}); dist[0]={0, 1}; priority_queuepq; pq.push({0, 0}); while(!pq.empty()){ long long dis=pq.top().first; int node=pq.top().second; pq.pop(); for(auto it : adj[node]){ int adjNode=it.first; long long edgewt=it.second; if(dis+edgewt < dist[adjNode].first) { dist[adjNode]={dis+edgewt, dist[node].second}; pq.push({dist[adjNode].first, adjNode}); } else if(dis+edgewt == dist[adjNode].first) { int count=dist[adjNode].second; dist[adjNode]={dis+edgewt, (count+dist[node].second)%mod}; } } } return dist[n-1].second; }

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@factsworlda2k547]

if Graph contains Multiedges from node 6 to 7 suppose no. of edges 3 then -- can we take this approach ? ways[adjNode] = ways[adjNode] + ways[node]*(6 to 7 multiedges number) 22:12

[@hemachel175]

Understood. Great work

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@swarajsonwane106]

Great explanation! Really appreciate the work you put in. Thanks ! You mis-spelled 'secoond' at 20:33. So no errorless at one go(just for fun)

[@KESHAVRAJ-l9p]

"i am proud of my self" man u should be.

[@kaichang8186]

understood, thanks for the great video

[@valorantfever3990]

Please also explain why normal queue doesnt work here. THANKS!

[@priyanshvatsal9791]

Normal queue will also work but in that case you'll explore all paths (unnecessary). But if you use PQ then if we arrive at a node which is already visited with less distance , then we don't need to explore that path further . This will save time .

[@AdityaPratapSingh-ss8wg]

@@Rohan-ns3ed exactly !!!

[@dibyamohanacharya9783]

Please do video on minimum swaps to sort array

[@H6_winger]

Thank u sir , u explained nicely

[@SahilTyagi-m8m]

hello striver i just want to ask why queue is not working for this question why only priority queue because with queue also we are going to travel every case

[@AdityaPratapSingh-ss8wg]

my exact same question. Any solution to this so far?

[@harshalsanap8978]

Whole Edtech YT creators are slowly started playing their game of selling paid courses and on the other side, there is this guy who is continuously creating more and more free content so that even the poorest can learn for free. Hatsoff man, it takes courage to spend your time teaching for free, he would have earned millions by selling but he didnt .🫡

[@Learnprogramming-q7f]

Thank you bhaiya

[@namesurname2223]

Plz help me understand one thing in the intuition, lets say I can reach node V via node U (ways[U] = 2) so ways[V] will also become 2 (assuming ways[V] was 0 earlier), now is it possible that ways[U] will increase to 3 in future then how will ways[V] will get update as we are not further pushing same pair in queue. I know I am missing something , but plz let me know If my question is not clear plz let me know

[@kushagrajain9493]

Hi, this situation will not come because here we are using priority queue, so as the distance of upcoming nodes will be greater then current node, so firstly all the updations on the current node will be done and upcoming nodes will be updated later on.

[@akashsahu2571]

great dry run

[@mohammadhanif3016]

appreciate your efforts bro !!..keep it up

[@khushiii8672]

understood bhaiya!!!

[@SumitKeshariMCS]

Amazing Explanation!!

[@sahelidebnath5085]

In the place of ways array i added all the ways in the priority which is having

[@niharikakumar1533]

Understood sir 🙂

[@parshchoradia9909]

Understood Sir!

[@pulkitjain5159]

apki DP series dekhne ke logic toh easily guess hogya tha 😆

[@ShivamBharatvanshi]

thanks Striver

[@giridharanpasupathi]

mass thalaiva

[@natural_lifstyle3727]

@takeUforward bhaiya why mod at last return step also if we took mod (at each step (in loop)) previously ?

[@dolbyagarwal9316]

Hi Striver, thanks for the amazing video. One thing, my Python version of code passed gfg Test cases but same code is failing on leetcode for last testcase and I can't figure out why.

[@sanketmudholkar2889]

Just take long instead of int (everywhere) and it will pass all the test cases .

[@harshdasila6680]

@@sanketmudholkar2889 Still in one case its giving me wrong answer in Leetcode even i have changed it to long long .

[@takeUforward]

@@harshdasila6680 read pinned comment

[@dolbyagarwal9316]

Thanks for the advice.

[@shubhamkewat2496]

jordaar

[@rishavkumar2182]

Good explanation!!

[@ankitranjan88]

[@SharmaSir-i6p]

why can't we use queue instead of priority queue in this question ? By the way ,appreciate your hardwork.

[@abhishekmehrotra4210]

Since the distance between nodes is not constant.. we can replace pq with q only when the edge weights are similar or increase in the same fashion.

[@gautamgupta7148]

@@abhishekmehrotra4210 can you please elaborate more

[@ArpitKumar-yo6up]

Bhai iss sawaal ne bahut rulaya

[@devans1244]

can we do this with dfs AND we store all path and its count to reach destination.

[@sunilpanchal1498]

Understood as always

[@itsatul_]

bhai i am having this runtime error and i tried resolving it i even changed all the varaibles to ll what should i do??

[@TarunKumarSaraswat]

thanks

[@adarshsingh2630]

TESTCASE 13 CASE: CHANGES MADE: CHANGE DATA TYPES TO LONG LONG FROM INT WHEREVER POSSIBLE class Solution { public: int countPaths(int n, vector &roads) { // Creating an adjacency list for the given graph. vector adj[n]; for (auto it : roads) { adj[it[0]].push_back({it[1], it[2]}); adj[it[1]].push_back({it[0], it[2]}); } // Defining a priority queue (min heap). priority_queue pq; // Initializing the dist array and the ways array // along with their first indices. vector dist(n, LONG_LONG_MAX), ways(n, 0); dist[0] = 0; ways[0] = 1; pq.push({0, 0}); // Define modulo value int mod = (int)(1e9 + 7); // Iterate through the graph with the help of priority queue // just as we do in Dijkstra's Algorithm. while (!pq.empty()) { long long dis = pq.top().first; long long node = pq.top().second; pq.pop(); for (auto it : adj[node]) { long long adjNode = it.first; long long edW = it.second; // This ‘if’ condition signifies that this is the first // time we’re coming with this short distance, so we push // in PQ and keep the no. of ways the same. if (dis + edW < dist[adjNode]) { dist[adjNode] = dis + edW; pq.push({dis + edW, adjNode}); ways[adjNode] = ways[node]; } // If we again encounter a node with the same short distance // as before, we simply increment the no. of ways. else if (dis + edW == dist[adjNode]) { ways[adjNode] = (ways[adjNode] + ways[node]) % mod; } } } // Finally, we return the no. of ways to reach // (n-1)th node modulo 10^9+7. return ways[n - 1] % mod; } };

[@arka6302]

For those whose test cases are failing use this code as reference: U need to convert everything to long long and use 1e18 ``` #define ll long long class Solution { public: int countPaths(int n, vector& roads) { // code here ll u,v,w,node,d,adjnode,edw; vectoradj[n]; // vectoradj; for(auto i:roads) { u=i[0]; v=i[1]; w=i[2]; adj[u].push_back({v,w}); adj[v].push_back({u,w}); } vectordist(n,1e18),ways(n,0); dist[0]=0; ways[0]=1; priority_queuepq; pq.push({0,0}); ll mod=(ll)(1e9+7); while(!pq.empty()){ d=pq.top().first; node=pq.top().second; pq.pop(); for(auto i:adj[node]) { adjnode=i.first; edw=i.second; if(d+edw

[@SaiKumar-0781]

Thanks striver

[@rishavkumar2182]

Great energy!!

[@Abhishekkumar-im7lb]

The question states that their is bidirectional roads between some intersections ..so how can we assume that it is undirected graph.

[@adarshatiiest]

i Was stuck with intution of just counting incoming paths . Striver wow .

[@-VLaharika]

Understood 👍

[@kiransequeira6152]

Thank you

[@juniorboy1903]

Maja aa gaya 😀😊😇