Many times I come here just so that someone reads the description of the problem to me :))
@greatfate4 ай бұрын
dijkstra is ultimate general tool but floyd mayweather is both easier to code and more efficient here
@abhinavchoukse23574 ай бұрын
dude it's Floyd Warshall Algorithm... floyd mayweather is a boxer 😂😂
@salim4444 ай бұрын
Floyd Mayweather be punching them vertices up 😂. edit: سيف النار اقوى من فلويد 😅
@roderickli65054 ай бұрын
i thought it was v^3 compared to djstra wouldnt djstra be better?
@tuandino69904 ай бұрын
@@roderickli6505 if you terminate dijkstra early it might beat floyd mayweather
@dimitristolias25514 ай бұрын
An optimization to this solution would be to store the pairs of characters you need to convert and run dijkstra only on those pairs, terminating when you find min distance to target char.
@freecourseplatformenglish28294 ай бұрын
Solved it on my own. Dijkstra + memorization.
@pratyushthakur84784 ай бұрын
I solved it but was getting a tle this really helped
@freecourseplatformenglish28294 ай бұрын
Yes, the length of string is long so you need to memorize the repeated calls.
@pratyushthakur84784 ай бұрын
@@freecourseplatformenglish2829 I wasn’t using dijkstra tho I had a recursive dfs like function
@AndrewKoulogeorge4 ай бұрын
Definitely talk about Floyd for this solution !
@m.kamalali4 ай бұрын
Thanks for the great effort, I think Dijkstra could be optimised if we only push to the heap when the new cost is less than the minimum cost we already seen
@rostislav_engineer4 ай бұрын
Thanks for this video!
@MuscleTeamOfficial4 ай бұрын
Thx mr
@jaiveersingh55384 ай бұрын
Fyi Dijkstra's rhymes with "like straws", not "pick straws"
@saurabhgodse84824 ай бұрын
I have one doubt, where are we checking min cost if we reach same node again ?
@theich43034 ай бұрын
If we reach the same node again, the check in line 13 will be True and we continue with the next node. The heap guarantees that if we reach a node for the first time, it will be with the lowest cost.
@pastori26724 ай бұрын
easy af 💯
@fancypants60624 ай бұрын
🤩
@ashabyesrab51664 ай бұрын
How did you know that there could not be a cycle in the graph?
@vikneshcs482423 күн бұрын
How tc is o(n+m)
@Empire-jx5wk4 ай бұрын
Graph 😮
@vietnguyenquoc49484 ай бұрын
My dumbass brain did think of looping dikjstra, but somehow I thought it woukd be nsquare or more so. Darn it need to improve the complexity calculation
@immortal40914 ай бұрын
Time Complexity: O(ELog(V)) it is showing this time complexity on leetcode am I missing something and can someone explain
@ParodyCSEDept4 ай бұрын
How about Floyd Warshall algorithm?
@tranminhquang45414 ай бұрын
I think the floyd warshall algo is only used when we know the depth of the tree with root being the source . That's just my guess. Correct me if I'm wrong!
@jamestwosheep4 ай бұрын
@@tranminhquang4541 I managed to use Floyd-Warshall on this problem - that algo is useful whenever you need the shortest path from every node to every other node. So as far as I understand it, I don't think there's any size/depth or start/source limitations on it. But the algo does take O(V^3) time complexity to run (V being the number of verticies/nodes), which isn't too bad for this problem because V = 26 in worst case, so O(26^3) is still O(1). Edit: I should also mention that if there's no valid path from node A to node B, Floyd-Warshall will simply give you an infinite cost to go between those 2 nodes (assuming Infinity is how you decide to mark an invalid path). Long story short, kzbin.info/www/bejne/aoC0lnargb6dY5Y has a really good explanation on Floyd Warshall.
@manimtirkey8614 ай бұрын
@@jamestwosheep Agreed! the moment you encounter an infinite cost you can break the loop and return -1.
@tranminhquang45414 ай бұрын
@@jamestwosheep I'm wrong then . Sorry !
@jamestwosheep4 ай бұрын
@@tranminhquang4541 Oh please, no need to be sorry! I'm on my own algorithms study journey at the moment and this stuff is hard! But, I've found that being wrong and understanding the misunderstanding has been a pretty good way to learn so far. So please, don't be sorry, and good luck to you for your own studies! :D
@anshdholakia7144 ай бұрын
another graph problem :fire:
@saruhasan91454 ай бұрын
class Solution { private static Map dijkstra(char src, Map adj) { Comparator comparator = new Comparator() { @Override public int compare(Pair p1, Pair p2) { return Integer.compare(p1.getKey(), p2.getKey()); } }; Queue heap = new PriorityQueue(comparator); heap.add(new Pair(0, src)); Map min_cost_map = new HashMap(); while(!heap.isEmpty()) { Pair pair = heap.poll(); int cost = (int)pair.getKey(); char node = (char)pair.getValue(); if (min_cost_map.containsKey(node)) { continue; } min_cost_map.put(node, cost); List neighbors = adj.get(node); if(neighbors != null) { for(Pair nei_pair : neighbors) { char nei = (char)nei_pair.getKey(); int nei_cost = (int)nei_pair.getValue(); heap.add(new Pair(nei_cost + cost, nei)); } } } return min_cost_map; } public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) { Map adj = new HashMap(); for(int i = 0; i < cost.length; i++) { if(!adj.containsKey(original[i])) { adj.put(original[i], new ArrayList()); } adj.get(original[i]).add(new Pair(changed[i], cost[i])); } Map min_cost_maps = new HashMap(); for(int i = 0; i < source.length(); i++) { char src = source.charAt(i); if(min_cost_maps.containsKey(src)) { ; } else { min_cost_maps.put(src, dijkstra(src, adj)); } } long res = 0; System.out.println(min_cost_maps); for(int i = 0; i < source.length(); i++) { char src = source.charAt(i); char dest = target.charAt(i); if (!min_cost_maps.get(src).containsKey(dest)) { return -1; } res += (int)min_cost_maps.get(src).get(dest); } return res; } } Good luck 🙂
@BayernRocks20204 ай бұрын
Please re consider the neetcode fees (for Indians it's way too high)🙏🙏🙏🙏🙏
@moabd75754 ай бұрын
thanks you're the best! but i hope that you depend less on python tricks next time, to apply the solution on all languages
@fancypants60624 ай бұрын
He explained how to write it without "tricks" in the video. Also, these "tricks" are just how to write something in 1 line instead of 3 lines. There are some crazy one-liners that are possible in python, but he doesn't use those, he keeps things very basic so that it can be easily converted.
@chaitanyasharma62704 ай бұрын
djikstra giving TLE, please show floyd warshall solution
@chaitanyasharma62704 ай бұрын
my gjikstra solution public class Solution { Dictionary g=new Dictionary(); public long MinimumCost(string source, string target, char[] original, char[] changed, int[] cost) { for(int i=0;i
@chaitanyasharma62704 ай бұрын
i memoized my solution it worked public class Solution { Dictionary g=new Dictionary(); Dictionary dp; public long MinimumCost(string source, string target, char[] original, char[] changed, int[] cost) { dp=new Dictionary(); for(int i=0;i
@陳冠霖-q6y4 ай бұрын
@@chaitanyasharma6270 you can run dijkstra algo at most 26 times, using dp to memorize and avoiding repeat compution if duplicate.