Find Edges in Shortest Paths | Dijkstra's Algo | Full Intuition | Leetcode 3123 | codestorywithMIK
Vložit
- čas přidán 6. 09. 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 46th Video of our Playlist "Graphs : Popular Interview Problems" by codestorywithMIK
Dijkstra's Algo (Part-1) - • Dijkstra's Algorithm |...
Dijkstra's Algo (Part-2) - • Dijkstra's Algorithm |...
In this video we will try to solve another very good problem based on Dijkstra's Algorithm : Find Edges in Shortest Paths | Dijkstra's Algorithm | Complete Intuition | Leetcode 3123 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Find Edges in Shortest Paths | Dijkstra's Algorithm | Complete Intuition | Leetcode 3123 | codestorywithMIK
Company Tags : Will update soon
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
Approach Summary :
The provided code implements an approach to find paths in an undirected graph that satisfy certain conditions. Here's a summary of the approach:
1. **Shortest Path Calculation**: The `getShortestPath` function calculates the shortest distance from a given source node to all other nodes in the graph using Dijkstra's algorithm. It uses a priority queue (`pq`) to prioritize nodes based on their current distance from the source.
2. **Path Evaluation**: The `findAnswer` function constructs the graph from the given list of edges and then computes the shortest paths from both the starting node and the ending node using the `getShortestPath` function.
3. **Path Validation**: For each edge in the list of edges, the code checks if there exists a path from the starting node to the ending node via the edge such that the sum of distances from the starting node to the edge, from the edge to the ending node, and the weight of the edge itself equals the total shortest distance from the starting node to the ending node. This check is performed in both directions since the edges are undirected.
4. **Result Generation**: The function returns a boolean vector indicating whether each edge satisfies the conditions or not.
Overall, the approach efficiently computes shortest paths in the graph and checks whether certain paths meet the required criteria, providing a solution to the problem at hand.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#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 #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
Correction : Time complexity of Dijkstra is O(ElogV) . My bad for the silly 😅
Sir please upload 3rd one I have tried greedy it is too confusing
i think greedy will fail. dp will be used
I solved using dp.
First 10 minutes are enough to solve the problem, thanks 😊
We can also do this by maintaining a Parent array, and storing min path for every node, and then for the query just search if that edge is present in our array
I could not solve this due to time but now I think I could have solved it by making 1-2 mistakes. thank you so much for improving my dsa. I am finally now able to solve 2-3 qns in leetcode contests
oneof the best explanation so far.🎉❤
Means a lot ❤️❤️🙏🙏
Can you make video on this question with second approach using parent vector.
Plz solve The latest time to catch a bus using BINARY SEARCH approach.
Leetcode problem no.2332
Legend for a reason. 🔥🔥
Qn-4 made halwa
amazing explaination as usual
Minimum Number of Operations to Satisfy Conditions Sir please make video on this one
and yeah thanks to you i was able to solve 4rth question in todays contest for the first time ever
Awesome
bhai legend ho tum
bhaiya apke tarha story ko code mai badlne practice kaise kare please bhaiya share some way to do so.
Sir i have new doubth
1254. Number of Closed Islands
This code is work but if i change the dfs to logic for 4 direction and do nothing why it give wrong answer:
class Solution {
public:
bool dfs(int i,int j,vector &grid){
if(i=grid.size() || j>=grid[0].size()) return false;
if(grid[i][j]==1 || grid[i][j]==2) return true;
grid[i][j]=2; //when i found 0;
bool down = dfs(i+1,j,grid);
bool right = dfs(i,j+1,grid);
bool up = dfs(i-1,j,grid);
bool left = dfs(i,j-1,grid);
return down && right && up && left;
}
int closedIsland(vector& grid) {
int n = grid.size();
int m = grid[0].size();
int cnt=0;
for(int i=0;i
Thank You so much bhai ❤❤
Amazing ❤❤❤❤❤❤❤
Great Explanation sir!! Just one doubt i think Time complexity of Dijikstra is O(E*logV) and Not O(V+E).
Ah so sorry. My bad for this silly.
I added the correction in my Pinned Comment.
Thanks a lot ❤️❤️
weekly contest 394 question 3 ka bhi sol upload kardo pls...
bhaiya third question dp ke alwa koi aur approach se solve ho sakta hai kya .Agar ha toh Please ispar video bana dijiye.
bhaiya aapne jo java bala code he usme one test case pass nhi ho raha he aap ek bar chek kar lijiye;
Corrected.
Thanks a lot for pointing it out
Sir can you please share your dsa sheet ?
You can find the sheets link in this page -
github.com/MAZHARMIK
It has all details
Thank you ❤️❤️
bhai yeh jo apne visited se dijkstra ko optimize kra hai usse thoda aur explain kr skte ho??? yeah dijkstra ka part 3 video banaoge???
bhaiya vo visited vala optimization dhang se samajh nhi aaya
Actually it’s just used to avoid visiting an already visited node.
You would not want to visit an already visited node.
@@codestorywithMIK bhaiya,kabhi aap double dijkstra par video banao toh please yeh optimisation ka dry run bata dijiyega, mujhe doubt yeh hai ki agar vo node pehle visited toh Hui par kisi let say A node se vahan visit Kiya aur ab ki baar Jo visit kar rhe hai same node ko par hum kisi B node se vahan ke liye check kar rhe hain....
Sure, I will cover that 👍🏻
god English please
good bro