highly recommend all of you to do leetcode 118 - 120 (neetcode has all explanation videos) the structure is pretty similar that all of them are dealing with triangles btw great explanation and your solutions always inspire me, thanks a lot🙏🏻
bfs with bitmask instead of set. Look up how to do a bitmask, its actually surprisingly easy. The intuitive approach is to bfs because we want a shortest path, each bfs node will need to maintain a visited set though. Instead of an actual set, we use an integer bitmask. As you know, integers are represented as binary, ex: 00101. If we assign each node to a position in the binary representation, we can mark it visited by flipping the digit from 0 to 1. This yields a unique integer for each visited set. So If I want to mark the 0th node as visited my bitmask looks like this: 0001 (4 nodes total, 0,1,2,3). This yields the integer 1. Set the 0 and 3rd visited? 1001, int = 9. Here is the operation for setting a given bit as visited, bitmask |= (1
If poured was fixed could there be a DP solution? I'm thinking along the lines that you would have a base case since you know the total amount of champagne.
highly recommend all of you to do leetcode 118 - 120 (neetcode has all explanation videos)
the structure is pretty similar that all of them are dealing with triangles
btw great explanation and your solutions always inspire me, thanks a lot🙏🏻
Great explanation as always. But I found the 44.5 overflow at 4:40 to be very confusing. I am pretty sure it should be 49.5 as 2x 49.5 = 99.
Yep, my math was way off, sorry about that!
I coded after following your explaination and my code is exactly similar. Thanks dude. I have recently started doing Leedcode daily for last 5 days.
Kinda Pascal's triangle
I was worrying about some champagne will reach the end first. Didn’t think of processing it row by row is possible. Great explanation, thanks!
847. Shortest Path Visiting All Nodes :(
bfs with bitmask instead of set. Look up how to do a bitmask, its actually surprisingly easy. The intuitive approach is to bfs because we want a shortest path, each bfs node will need to maintain a visited set though. Instead of an actual set, we use an integer bitmask. As you know, integers are represented as binary, ex: 00101. If we assign each node to a position in the binary representation, we can mark it visited by flipping the digit from 0 to 1. This yields a unique integer for each visited set. So If I want to mark the 0th node as visited my bitmask looks like this: 0001 (4 nodes total, 0,1,2,3). This yields the integer 1. Set the 0 and 3rd visited? 1001, int = 9.
Here is the operation for setting a given bit as visited, bitmask |= (1
Don't think I'll ever be able to solve this in a real interview if I never did this question before :(
It's literally NEET CODE! Thank you
Simple and elegant, thanks for the effort! Keep it going :)
did the same, but i basically consider this a BFS where each row is a level of the tree
You are the saviour.
Genius.
If poured was fixed could there be a DP solution? I'm thinking along the lines that you would have a base case since you know the total amount of champagne.
Superb Explanation ...
Thanks lord, we have you!!🙂
nice way of explaining👍
Bro please upload leetcode video daily
another one already wowz
this one was pretty cool
pretty hard for a med
Guess you meant 49.5 and not 44.5 at 5.08 for 100 example.
looks like the dp problem
ebat' traxatel
i thought it was a dp problem
Same, spent forever trying to think of a base case. I guess sometimes the most straightforward solutions are the right ones
lol