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?

[@lavanya_m01]

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!

[@NaqushabNeyazee]

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

[@rawallon]

Who needs asmr when we got this

[@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!

[@fightmeonclubpenguin7748]

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

[@siddharthr594]

What else did you get?

[@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!

[@orangethemeow]

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

[@ThantHtooSan-p3f]

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

[@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)

[@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.

[@hassan7569]

Another day, another NeetCode video.

[@fa11en1ce]

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

[@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

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

[@MP-ny3ep]

Great explanation as always. Thank you !

[@YasirYSR]

in Love with this channel

[@achint227]

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

[@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!

[@nathamuni9435]

Ooh 🤯 every intuitive

[@utkarshagupte1178]

Wonderful explanation.

[@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

[@pastori2672]

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

[@metarus208]

thank you for soldiering on

[@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

[@tianmingguo8271]

Great explanation.

[@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

[@shinsatori184]

Thanks for the explanation. So clear!

[@Deschuttes]

Thanks need, please keep going.

[@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

[@telnet8674]

thank you

[@nishantingle1438]

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

[@dpynsnyl]

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

[@sudhaarulmani9218]

Thank you 🙏

[@irarose3536]

Thanks!

[@beyond-convention]

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

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

[@mohithadiyal6083]

What is Neetcode's leetcode profile?

[@barnetthan9391]

ur a goat

[@techenthusiast3966]

Which softwares do you use to record and draw?

[@NeetCode]

I use Paint3D

[@itsmejaypatel]

can we use dfs?

[@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…

[@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.