Path with Maximum Probability | Using Dijkstra's | GOOGLE | Leetcode-1514 | Live Code
Vložit
- čas přidán 26. 06. 2023
- *******Watch my Dijkstra's Algorithm Video and copy paste the same code with slight variation - • Dijkstra's Algorithm |...
This is the 30th Video on our Graphs Playlist.
In this video we will try to solve a very good Graph Problem "Path with Maximum Probability " (Leetcode - 1514)
This is nothing but just a simple variation of Dijkstra's Algorithm.
I am promising you, this problem will become easy once you are done with this video.
If you have been following my "Graph Concepts & Qns" playlist , then these Qns will become very easy. Find the Link for that below.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Path with Maximum Probability
Company Tags : GOOGLE
My solutions on Github : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/path-wi...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips
#interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook
I went to the Graph concepts playlist and revised Dijkstra from there, believe me I didn't had to watch this video to solve this problem. 😇🥰
You just made my day Tauquir ❤️❤️❤️
And Congratulations on your new internship offer ❤️❤️❤️
Keep growing. We have to achieve more and more and more
@@codestorywithMIK thanks bhaiya.... You have played an important role in my life for getting this opportunity. The OA round which was based on DSA was a cakewalk for me. 🥰🥹
so glad to know.
Please always keep following points in your mind -
1) Keep working hard, never settle.
2) Enjoy as well in life
3) Work hard to fulfill your dreams + your PARETN’S dreams
All the best
@@codestorywithMIK ❣️
i had already seen dijkstra video so i was on the right the track but i was using min heap 😅 thanks for the explanation.
❤️❤️
No can teach Graph like you on internet.
I will repeat, you are the "KING OF GRAPHS"
Literally no one teaches like you bro
You have insane level of clarity on how to teach ❤❤❤
very good explanation
Literally no one teaches like you bro, thanks for the amazing explanation
❤️❤️
Yuppp...thanks a lot
Dijkstra's Based Problems -
github.com/MAZHARMIK/Interview_DS_Algo/tree/master/Graph/Dijkstra'a%20Based%20Problems
Dijkstra's Videos in my Graph Concepts & Qns Playlist - czcams.com/video/xQ3vjWwFRuI/video.html
Thank you to all of you for your kind reviews and comments❣
Amazing explanation👍
Awesome ❤
Someone trade said - GOAT of DSA
King of Graphs ❤
Easy and Best Explaination As Always
Thank you ❤️
u made it a cakewalk!
thanks❤
Means a lot ❤️❤️
Please post today's POTD - 864. Shortest Path to Get All Keys
those who know dijkstra its easy for them
Indeed
❤
Why using Queue results in lesser runtime when compared to maxheap?
bhai good explain ,i want to also make such videos with clarity ,can i get a chance to learn from u ,how u do that
Thank you😊
For making the video, I don’t have any fancy equipment. I just do screen recording of my ipad and write on it.
@@codestorywithMIK bhai aap editing nahi krte kya ,kyuki aese toh sahi se video nahi aati 🥲
woh janna hn kese krte hon
@level_up.1908 As of now, I only record simply and upload it.
Soon i will buy some equipments for good editing and quality.
Hope to help you all in better way
Gives your codeforces and leetcode profile link
kyu bro ?
Java code for this ques-
class Pair{
int node;
double prob;
Pair(int node,double prob){
this.node=node;
this.prob=prob;
}
}
class Solution {
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
List adj=new ArrayList();
for(int i=0;i Double.compare(b.prob,a.prob));
q.offer(new Pair(start,1.0));
while(!q.isEmpty()){
Pair temp=q.poll();
int u=temp.node;
double upb=temp.prob;
if(u==end) return upb;
for(Pair it:adj.get(u)){
int v=it.node;
double vpb=it.prob;
if(upb*vpb>prob[v]){
prob[v]=upb*vpb;
q.offer(new Pair(v,prob[v]));
}
}
}
return 0.0;
}
}
Thanks a lot ❤️
Thanks a lot
@@codestorywithMIK ❤❤
bhai why can't we use dfs?
here is the code
class Solution {
public:
double dfs(vector& list, int sv, int end, vector& visited){
if(sv == end){
return 1;
}
visited[sv] = true;
double answer = 0;
for(int i=0; i
@@mileshsoni5016 COZ IT WILL GIVE TLE
class Solution {
public:
void dfs(unordered_map& adj, vector& visited, double& maxi, double ans, int u, int c) {
if(u == c) {
maxi = max(maxi, ans);
return;
}
visited[u] = true;
for(auto& x : adj[u]) {
int k = x.first;
double l = x.second;
if(!visited[k]) {
dfs(adj, visited, maxi, ans * l, k, c);
}
}
visited[u] = false; // backtrack to allow other paths
}
double maxProbability(int n, vector& a, vector& p, int s, int e) {
unordered_map adj;
for(int i = 0; i < a.size(); i++) {
int u = a[i][0];
int v = a[i][1];
double d = p[i];
adj[u].push_back({v, d});
adj[v].push_back({u, d});
}
vector visited(n, false);
double maxi = 0.0;
double ans = 1.0;
dfs(adj, visited, maxi, ans, s, e);
return maxi;
}
};
SEE IT GAVE TLE