The space complexity is actually O(log 10000 to the base 8) because each combination only has 8 neighbor combinations, and the space needed for visited can be reduced by having a array of Boolean of size 10k (that is 10kb) or using a bit set (size 1.25 KB)
Great explanation! This one was tricky because it uses the word "minimum" so I totally thought it was a DP problem and tried to attack it using DFS + memoization and I got stuck. But your explanation was really clear! :)
I think DFS + memoization still work if you keep update a minimum path variable and search all the working path? BFS can ensure when you first get the target, you are in the shortest path, so you don't need to search all the working path
For 1000 (10^4) possible combinations, we are also generating lock states within the outer while loop. Shouldn't that make the time complexity O(N * 10^4)?
Hi Neetcode thanks for your neat explaination...can you pls solve leetcode 465. Optimal account balance problem...this question asked by Google and uber...and this problem is pretty unique!
Hi Neet! Thanks for your videos! They are really helpful! Could you pls do 987. Vertical Order Traversal of a Binary Tree? This is a really popular question for FB (top 10). I think it will help many people! Thanks
I wonder if A-Star search algo would improve average run time efficiency. It basically applies an estimation-cost-to-destination. depending on current_steps_taken + estimation-cost-to-destination, it will prioritize which state in the queue should be processed next. Reason i say i wonder, is because the worst case would be nlgn, which is worse than O(10000) in this case
More of a Python question. How come we didn't return the res in the helper function but the for loop in the main function picked the child of children up? How come we can iterate through the res without having it returned? Thanks
Will it be a better approach to reverse the problem and start from target as root node and then try and reach 0000... ? I think it might save us some calculation of nodes not needed to trace in the tree. What do you think ?
I was wondering that too. Have seen others do whiteboard/pen with OneNote. But I'm sure there are better options than OneNote available (especially on Mac).
I have written code like this in c++ but this is leading to TLE and I cant figure out why ? Can anyone help class Solution { public: vector children(string x) { vector v; for (int i=0; i
Hi, even though it's been over 9 months, I'd be happy if this information is still relevant. Your code didn't work because of the line if (find(s.begin(), s.end(), child) == s.end()). You don’t need to use iteration from beginning to end because it's inefficient. Instead, you can use the more efficient find() function of an unordered set, like s.find(child) == s.end(). This approach reduces the time complexity to O(1) when you change from set to unordered_set. Here's an example: class Solution { public: vector children(string x) { vector v; for (int i = 0; i < 4; i++) { char a = (((x[i] - '0') + 1) % 10) + '0'; v.push_back(x.substr(0, i) + a + x.substr(i + 1)); char b = (((x[i] - '0') - 1 + 10) % 10) + '0'; v.push_back(x.substr(0, i) + b + x.substr(i + 1)); } return v; } int openLock(vector& deadends, string target) { if (find(deadends.begin(), deadends.end(), "0000") != deadends.end()) return -1; queue q; q.push({"0000", 0}); unordered_set s({"0000"}); //
Python Code: github.com/neetcode-gh/leetcode/blob/main/752-Open-the-Lock.py
Java Code: github.com/ndesai15/coding-java/blob/master/src/com/coding/patterns/bfs/OpenLock.java
can you make a video how we get a job at google
get good at leetcode? will it give me a job?
What was ur first thought when u saw this problem?
I thought you won't be posting anymore since you got a job at Google, your videos helps a lot
He’s been there for a year already!
@@chinesemimi That in covid years of human years?
Just in case if you didn't know, -1%10 gives 9 in python. so we don't have to add 10 and perform modulo. Great video btw!
I tired to search this problem in your channel this morning but couldn’t find the video, and then you posted this video after I had lunch!
At this point I have started listening to your content as a podcast. Great work!!
Who needs asmr when we got this
I got this question in my Amazon interview a couple months ago!
What else did you get?
I was so scared of this problem before I saw the graph and explanation, your explanations are golden.
Thank you, this why I love this channel the dedication. One day I will make you proud!
It's so smart to add deadends to the visited set
The space complexity is actually O(log 10000 to the base 8) because each combination only has 8 neighbor combinations, and the space needed for visited can be reduced by having a array of Boolean of size 10k (that is 10kb) or using a bit set (size 1.25 KB)
appreciate your efforts and big thanks to your explanation. It helps me not to quit practicing the leetcoode
Appreciate your effort and don’t stop posting
Another day, another NeetCode video.
Great explanation! This one was tricky because it uses the word "minimum" so I totally thought it was a DP problem and tried to attack it using DFS + memoization and I got stuck. But your explanation was really clear! :)
I think DFS + memoization still work if you keep update a minimum path variable and search all the working path? BFS can ensure when you first get the target, you are in the shortest path, so you don't need to search all the working path
Would've been interesting to see this solved using a* if you use each lock digit as a coordinate
Simple and straightforward explanations. I'd appreciate it if you could extend the time allotted for explaining time and space complexity.
For 1000 (10^4) possible combinations, we are also generating lock states within the outer while loop. Shouldn't that make the time complexity O(N * 10^4)?
Great explanation as always. Thank you !
felt terrible comming up with this solution just to know its basically as efficient as you can get it 😆👍
Hi Neetcode thanks for your neat explaination...can you pls solve leetcode 465. Optimal account balance problem...this question asked by Google and uber...and this problem is pretty unique!
in Love with this channel
Ooh 🤯 every intuitive
Hi Neet! Thanks for your videos! They are really helpful! Could you pls do 987. Vertical Order Traversal of a Binary Tree? This is a really popular question for FB (top 10). I think it will help many people! Thanks
I wonder if A-Star search algo would improve average run time efficiency. It basically applies an estimation-cost-to-destination. depending on current_steps_taken + estimation-cost-to-destination, it will prioritize which state in the queue should be processed next. Reason i say i wonder, is because the worst case would be nlgn, which is worse than O(10000) in this case
Wonderful explanation.
thank you for soldiering on
I was wondering if this could be solved by implementing a bidirectional search ... would be more efficient
Hi your videos are amazing
Please share your interview experience
Great explanation.
Thanks for the explanation. So clear!
Thanks need, please keep going.
Once you see 3:01 then its just good ol' BFS
More of a Python question. How come we didn't return the res in the helper function but the for loop in the main function picked the child of children up?
How come we can iterate through the res without having it returned?
Thanks
thank you
Will it be a better approach to reverse the problem and start from target as root node and then try and reach 0000... ? I think it might save us some calculation of nodes not needed to trace in the tree.
What do you think ?
it would be literally the same, the start and end positions don't matter
Thank you 🙏
Shouldn't we have added "0000" to the visit set in the beginning?
Thanks!
your videos are very good. what tools do you use to create videos
Who has an idea what tool neetcode use for presentation? the whiteboard/pen part? Thanks
I was wondering that too.
Have seen others do whiteboard/pen with OneNote.
But I'm sure there are better options than OneNote available (especially on Mac).
ur a goat
What is Neetcode's leetcode profile?
Which softwares do you use to record and draw?
I use Paint3D
can we use dfs?
Shouldn’t “0000” be added to the visit set as well? What happens when children(1000) returns “0000”, wouldn’t that cause an infinite loop?
It won’t cause an infinite loop but the queue will have “0000” appended to it twice. I think…
I have written code like this in c++ but this is leading to TLE and I cant figure out why ? Can anyone help
class Solution {
public:
vector children(string x) {
vector v;
for (int i=0; i
Hi, even though it's been over 9 months, I'd be happy if this information is still relevant.
Your code didn't work because of the line if (find(s.begin(), s.end(), child) == s.end()). You don’t need to use iteration from beginning to end because it's inefficient. Instead, you can use the more efficient find() function of an unordered set, like s.find(child) == s.end(). This approach reduces the time complexity to O(1) when you change from set to unordered_set.
Here's an example:
class Solution {
public:
vector children(string x) {
vector v;
for (int i = 0; i < 4; i++) {
char a = (((x[i] - '0') + 1) % 10) + '0';
v.push_back(x.substr(0, i) + a + x.substr(i + 1));
char b = (((x[i] - '0') - 1 + 10) % 10) + '0';
v.push_back(x.substr(0, i) + b + x.substr(i + 1));
}
return v;
}
int openLock(vector& deadends, string target) {
if (find(deadends.begin(), deadends.end(), "0000") != deadends.end()) return -1;
queue q;
q.push({"0000", 0});
unordered_set s({"0000"}); //
You go into the code too soon. Not enough explanation. Sorry.