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
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.
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.
@@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; } }; ```
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;
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.
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.
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;
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 ❤️
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.
// 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; }
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.
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)
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]; } }
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
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; } };
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??
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 ?
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 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.
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.
For those whose all the testcases are not passing, no need to change int to long and 1e9 to 1e18. just fill the dist[] array with Integer.MAX_VALUE. keep everything as it was before and submit. That's it
I have taken this only, but the 13th case is failing. My code is- 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
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🥰😍
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 :)
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 .
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
Hey brother can you solve leetcode skiplist problem in Java
Bhiya graph k kitne lecture ayenge total approximately
testcases are failed on leetcode why??
Bhaiya is it the last video of this graph series??
test cases failing because of large test cases, just have long long and 1e9 to 1e18
16:46 "I get excited but that's how I teach" fr🙇♂🙇♂
which campus bro
@@doodlelordpilani
@@kushalloya4640 nice I'm from Goa. 26 batch?
@@doodlelord tiet '27
THIS GUYS IS ABSOLUTELY GENIUS. HE BREATHES CODING AND HE EXHALES TEACHING!!
His excitement for problem solving shows why he became so successful in this field.
Nobody can beat you in teaching style . You r such a gem.
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.
heyy you are in which year ?
@@Mohit_Q 3rd year
currently doing tree series just here to appreciate your hard work !!thanks a lot for this amazing content.
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.
*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
Still its giving me wrong answer for last test case
@@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;
}
};
```
Thanks dude😊
what to do in java? there isnt long long
thanks bro
The excitement and enthusiasm on your face while teaching is priceless
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
}
}
Thanks man!
thanks for the help
thanks for help
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.
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.
TLE because in dfs you might visit each node repeatedly.
"Understood" and energy was super amazing in this video 😁 .
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
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.
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;
in gfg also we get error at testcase 13 due to this problem
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 ❤️
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.
This problem has already been solved by you in one of old live sessions, thanks for the nice explanation.
For GFG Test Case 13 take Arrays.fill(dis,Integer.MAX_VALUE) insted of Arrays.fill(dis,(int)1e9+7);
but it is giving answer 2
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
// 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;
}
UNDERSTOOD,GOD OF GRAPH (STRIVER) U GRAPH SERIES IS FANTASTIC ,SUPARB,DONT HAVE WORS
In the place of ways array i added all the ways in the priority which is having
Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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.
Thank you
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)
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
solved it myself, thanks for this
Errorless code at one go is an emotion 🙂
Understood! So amazing explanation as always, thank you very much!!
Dry run was super Amazing💪. Understood!
"i am proud of my self" man u should be.
probably the best question i have learned from striver bhaiya series🤩
Understood , thankyou for making these videos 😇😇
solved before watching video...thanks🙏
Excellent Dry Run !! Understood
Thank you sir 🙏
understood😊😊 Thankyou bhaiya for making such amazing vdos.
Solid explanation🔥 kudos to you man!!!
Understood❤, Excellent Teaching
Amazing Explanation bro🔥loved it❤
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];
}
}
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
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;
}
};
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)
Very well explanation
Really great explanation !!
Waiting for next videos
Thank you Jiraiya sensei!
understood bhaiya
thank you so much for this awesome content
Thank you very much. You are a genius.
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??
yes otherwise u will not remember what u have solved
practice is the key here
which year u in?
@@krishanpratap3286 no bro 24 year old working professional
appreciate your efforts bro !!..keep it up
Works Fine on both Leetcode and GFG: ✅👇
int countPaths(int n, vector& roads) {
// Dijkstra Algo + ways array
int mod=1e9+7;
// adjacency list
vector adj[n];
for(auto i: roads)
{
int u=i[0];
int v=i[1];
int wt=i[2];
adj[u].push_back({v, wt});
adj[v].push_back({u, wt});
}
// distance, node
priority_queue pq;
pq.push({0, 0});
vector dist(n, 1e18);
vector ways(n, 0);
dist[0]=0;
ways[0]=1;
while(!pq.empty())
{
long distance=pq.top().first;
int node=pq.top().second;
pq.pop();
for(auto i: adj[node])
{
int adjNode=i.first;
int weight=i.second;
// first time coming with shortest distance
if(distance+weight < dist[adjNode])
{
dist[adjNode]=distance+weight;
pq.push({dist[adjNode], adjNode});
ways[adjNode]=ways[node]%mod;
}
else if(distance+weight==dist[adjNode])
{
ways[adjNode]=(ways[adjNode]+ways[node])%mod;
}
}
}
return ways[n-1]%mod;
}
Another brilliant video Sir
Understood Sir, Thank you very much
understood, thanks for the great video
loveddd your intuition and logic
Thank you bhaiya
loved the energy!!
understood bhaiya!!!
apki DP series dekhne ke logic toh easily guess hogya tha 😆
Understood. Great work
If you follow the DP series, this problem has same intuition as the "Number of LIS (Longest Increasing subsequences) problem".
jordaar
Thank u sir , u explained nicely
great dry run
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 ?
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
@@danushbasanaboyina1306 hi have you tried that queues solution ? Because it is giving WA and that's what @AmardeepMittal-qi1kx question is!!
@@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.
@@danushbasanaboyina1306 could you share your answer if possible or code link.
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.
For those whose all the testcases are not passing, no need to change int to long and 1e9 to 1e18. just fill the dist[] array with Integer.MAX_VALUE. keep everything as it was before and submit. That's it
I have taken this only, but the 13th case is failing. My code is-
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
Please do video on minimum swaps to sort array
thanks Striver
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🥰😍
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.
@@prateekpandey7449 Yes.
@prateek pandey didn't understand
@@vamsimudaliar8643 didn't understand
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
Understood Sir!
Bhai iss sawaal ne bahut rulaya
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 :)
use LONG_MAX in dist vector ..
Amazing Explanation!!
Maja aa gaya 😀😊😇
Understood sir 🙂
why can't we use normal queue data structure
Thanks striver
mass thalaiva
thanks
Understood as always
Good explanation!!
Understood 👍
Please also explain why normal queue doesnt work here. THANKS!
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 .
@@Rohan-ns3ed exactly !!!
dry run dekh ke to swaad aagaya
Thank you
Great energy!!
Understood!!
Amazingggg ❤
ye questions ka level bbhadte dekh, mereko cry aa rha hai
i Was stuck with intution of just counting incoming paths . Striver wow .
Awesome 👏👏
Amazing explanation
ENERGY LEVEL OPPP
Understood 😇
Understood!
maza aa gya vai