Open the Lock - Leetcode 752 - Python

[@NeetCode]

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

[@masternobody1896]

can you make a video how we get a job at google

[@masternobody1896]

get good at leetcode? will it give me a job?

[@thoufic907]

What was ur first thought when u saw this problem?

[@prajwal2583]

I thought you won't be posting anymore since you got a job at Google, your videos helps a lot

[@chinesemimi]

He’s been there for a year already!

[@rawallon]

@@chinesemimi That in covid years of human years?

[@NaqushabNeyazee]

At this point I have started listening to your content as a podcast. Great work!!

[@rawallon]

Who needs asmr when we got this

[@lavanyam3224]

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!

[@tinali7149]

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!

[@homyakMilashka]

I was so scared of this problem before I saw the graph and explanation, your explanations are golden.

[@ambroseaurelian9696]

Thank you, this why I love this channel the dedication. One day I will make you proud!

[@fightmeonclubpenguin7748]

I got this question in my Amazon interview a couple months ago!

[@siddharthr594]

What else did you get?

[@unitycatalog]

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)

[@jeevisiran21]

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!

[@orangethemeow]

It's so smart to add deadends to the visited set

[@user-sk7tp3wv4m]

appreciate your efforts and big thanks to your explanation. It helps me not to quit practicing the leetcoode

[@shahzebnaveed4776]

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)?

[@hassan7569]

Another day, another NeetCode video.

[@chenzhuo9]

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

[@yunaf4609]

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! :)

[@zhen9445]

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

[@fa11en1ce]

Would've been interesting to see this solved using a* if you use each lock digit as a coordinate

[@AchintBhat]

I was wondering if this could be solved by implementing a bidirectional search ... would be more efficient

[@showmethemoney824]

Appreciate your effort and don’t stop posting

[@wesammustafa9004]

Simple and straightforward explanations. I'd appreciate it if you could extend the time allotted for explaining time and space complexity.

[@MP-ny3ep]

Great explanation as always. Thank you !

[@YasirYSR]

in Love with this channel

[@nathamuni9435]

Ooh 🤯 every intuitive

[@pastori2672]

felt terrible comming up with this solution just to know its basically as efficient as you can get it 😆👍

[@amirbayat5713]

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

[@ks-mq3fm]

Hi your videos are amazing Please share your interview experience

[@Mcfly868]

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

[@commonsolutions8825]

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?

[@commonsolutions8825]

It won’t cause an infinite loop but the queue will have “0000” appended to it twice. I think…

[@utkarshagupte1178]

Wonderful explanation.

[@shinsatori184]

Thanks for the explanation. So clear!

[@vatsalsinha9273]

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 ?

[@MrKulkoski]

it would be literally the same, the start and end positions don't matter

[@tianmingguo8271]

Great explanation.

[@metarus208]

thank you for soldiering on

[@Deschuttes]

Thanks need, please keep going.

[@sudhaarulmani9218]

Thank you 🙏

[@telnet8674]

thank you

[@irarose3536]

Thanks!

[@beyond-convention]

your videos are very good. what tools do you use to create videos

[@mohithadiyal6083]

What is Neetcode's leetcode profile?

[@stanleyokoli212]

Who has an idea what tool neetcode use for presentation? the whiteboard/pen part? Thanks

[@CostaKazistov]

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).

[@dpynsnyl]

Shouldn't we have added "0000" to the visit set in the beginning?

[@nishantingle1438]

Once you see 3:01 then its just good ol' BFS

[@barnetthan9391]

ur a goat

[@techenthusiast3966]

Which softwares do you use to record and draw?

[@NeetCode]

I use Paint3D

[@jay-hk5oo]

can we use dfs?

[@nishadkanago4393]

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

[@ilanvinograd2631]

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"}); //

[@supremoluminary]

You go into the code too soon. Not enough explanation. Sorry.