Open the Lock - Leetcode 752 - Python
Vložit
- čas přidán 24. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/open-th...
Python Code: github.com/neetcode-gh/leetco...
0:00 - Read the problem
2:14 - Drawing Explanation
7:43 - Coding Explanation
leetcode 752
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#facebook #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
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?
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
Thank you, this why I love this channel the dedication. One day I will make you proud!
Appreciate your effort and don’t stop posting
appreciate your efforts and big thanks to your explanation. It helps me not to quit practicing the leetcoode
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!
Another day, another NeetCode video.
It's so smart to add deadends to the visited set
Thanks for the explanation. So clear!
Great explanation as always. Thank you !
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)
in Love with this channel
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.
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
Thanks need, please keep going.
Would've been interesting to see this solved using a* if you use each lock digit as a coordinate
thank you for soldiering on
Wonderful explanation.
Ooh 🤯 every intuitive
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!
Great explanation.
Thank you 🙏
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
Thanks!
Hi your videos are amazing
Please share your interview experience
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)?
Simple and straightforward explanations. I'd appreciate it if you could extend the time allotted for explaining time and space complexity.
your videos are very good. what tools do you use to create videos
thank you
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
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).
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
I was wondering if this could be solved by implementing a bidirectional search ... would be more efficient
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
felt terrible comming up with this solution just to know its basically as efficient as you can get it 😆👍
Which softwares do you use to record and draw?
I use Paint3D
What is Neetcode's leetcode profile?
Once you see 3:01 then its just good ol' BFS
ur a goat
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…
Shouldn't we have added "0000" to the visit set in the beginning?
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"}); //
can we use dfs?
You go into the code too soon. Not enough explanation. Sorry.