Valid Sudoku - Amazon Interview Question - Leetcode 36 - Python
Ғылым және технология
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 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
Problem Link: neetcode.io/problems/valid-su...
0:00 - Read the problem
4:49 - Drawing Explanation
8:50 - Coding Explanation
leetcode 36
This question was identified as an amazon interview question from here: github.com/xizhengszhang/Leet...
#valid #sudoku #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.
Пікірлер: 218
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Bro I'm literally in awe when you used simple division of indices with 3 to point to a particular square. Amazing as always.
@Flite999
Жыл бұрын
Agreed that is an elegant solution - what I have trouble with is getting to that kind of approach on my own!
@Cruzylife
Жыл бұрын
@@Flite999 you dont, you pick up patterns and practice similar problems.
@pinakadhara7650
Жыл бұрын
@@Flite999 Apart from practice, getting good in maths.
@henryfeng6300
Жыл бұрын
I used "Math.floor(r/ 3) * 3 + Math.floor(c / 3)" to get the index of sub-box
@rohitchand3853
Жыл бұрын
Sigma solution🤕
the row/3 and colum/3 idea is sooo neat i love it. I was having trouble iterating thru each of the squares. Im doing the NeetCode 150 on your website and I love that you have videos for each of the problems even if i get the right solution i look at your videos to see the alternative ways to solve it.
@servantofthelord8147
10 ай бұрын
You mean, it's so "neet" ;)
@dhavallimdiwala
8 ай бұрын
Additionally, we can convert into single number key instead of pair as a key. after doing devision by 3, we do 3*x+y. where x and y are indices from [0..2,0..2].
I haven't seen that much easy explanation of all the code you explained. It helps me to improve my overall logical skills. Thanks Bud!!
This guy is more than just a legend :) He is THE legend!
I never thought in this question that tuple (r//3, c//3) could be keys for defaultdict. Amazing!
@rishabhsetty3109
Жыл бұрын
keys for a dictionary have to be immutable so tuples work
@pahehepaa4182
Жыл бұрын
Same man. 2 years as a python developer still this popped
This is the best channel in the whole of KZread🔥
Omg!!!!! What an explanation. I literally spend an entire day trying this problem and you explained me clearly within these few minutes. You are the best teacher!!!!!
the best way to do this really, i had been struggling with this problem for a few days now, the sudoku solver really, i did the more complex way at first but i was worried that i would not be able to think of that solution in a coding test but this way is beautiful
The way you explain this problem is brilliant man! So glad I found your channel
This solution is simply beautiful. You have my respect, Neetcode.
@NeetCode
Жыл бұрын
Glad it was helpful!
this is the first medium problem that ive done myself which aligns exactly with the optimal solution, i feel accomplished 😅
Mind blown when you said you recorded on 4th of July!! It's been exactly one year! Thanks for everything you do
Amazing! Simply Amazing! Going to join your channel to help support the channel. Keep the videos coming.!
The implementation for the squares with floor division and using a tuple as the key is simply amazing!
excellent explanation! Thank you Neetcode!
Your way of explaining things and implementation is neet. Thanks for posting this!
Amazing explanation with some really easy and clean code!
Wow. This is an excellent solution. I used a list of lists to iterate through the grids. But, this is an amazing solution man. Keep up the great work.
This is the definition of NEAT CODE
Brilliant answers and explanations. Thank you very much
Naaaaaahhh I'm here to say it NeetCode is all time top 1 teacher when it comes to explaining and solving algorithm and data structure problems. My guy is HIM!!!
I came to almost the same solution! Instead of using hash maps for the rows, columns, squares, I just initialized them as arrays of size 9 with a set at each position. Using defaultdict(set) is definitely a neat way to make the row, columns, squares sets.
This makes my solution look like a crayon drawing of a 2-year-old. Awesome solution and well explained.
I hard coded the squares XD. This really opened my eyes. Thanks!
very well explained and very easy and intuitive
Amazing explanation. Thank you for the wonderful videos.
It couldn't have been more easier than this. I tried thinking whole day for the best way to solve it. But your solution is too simple yet very powerful. Thanks for the amazing content.
Sets in side of hashes with with the row/column as the key... that's pretty awesome!
You are awesome! The code very neat and understandable!! Thanks alot
Idk how i'd ever figure this one out without watching a video. As always, thanks!
Excellent explanation for every problem.
Thanks bro I had the right idea but didn't know how to implement detecting what box we are in. Row/3 and column/3 helped a lot
It's actually much easier to call them 3 - NxN matrices instead of 3 hash sets each of size NxN.
the java solution you provided in the website actually intimidated me from trying this problem but it was so simple... i think your java solution made it more complicated than it needed to be
Thanks So Much For Explanation!
thanks a lot. What you've done is truly delightful
Bro you are awesome. I hope you have a huge salary and you are working on some top IT company!
Funny you recorded this on the 4th of July.! I'm watching it on the 4th of July 2023
Thank you! Just used this method to solve the problem in C#
Thanks for making this video. It's a simple and intuitive explanation 🙏
Beautifully done
Wonderful explanation! Could you please do 229 Majority Element 2? I am interested in algorithm with O(n) time complexity and O(1) space.
I did it exactly the same way but I opted for just using 1 hashmap where the key was the number and the value was a tuple of (row, column, box number), then at every value I can just look up if it exists in the hashmap and compare each value in the tuple. I can't tell which solution would be better in terms of time complexity though since I would have to iterate all 3 values of my tuple after the constant lookup.
such an elegant solution. makes it so easy!
subscribed and liked, thank you for sharing your knowledge
great explanation brother!
preparing for doordash technical rounds, thanks neet
very clean and pythonic code
I did a 11 separated for loops solution in Swift, but still get beats 90% in time complexity and 60% in Space complexity.
Thanks man, liked
Thanks sir...before watching your solution when i solved this question my time complexity was like O(9^4) ....
Actually, time complexity will be O(1). because O(n^2) in our case is O(81) which is equal to O(1) as it's not depend on size of array.
awesome as usual! :)
Thanks a lot for your videos :)
Do sudoku solver next!
Thanks for the explanation, it was superb✔👌 I am sharing the C++ code for the same implementation below 👇: class Solution { public: bool isValidSudoku(vector&board) { int rowCheck[9][9] = {0}; //for checking rows int colCheck[9][9] = {0}; //for checking columns int subMatrix[3][3][9] = {0}; //for checking sub matrices/boxes for(int i=0;i
Thanks - most helpful
Can you do LC 1048 Longest String Chain? Watched a few other vids but can't quite wrap my head around it.
Please make a video for leetcode 37 Sudoku Solver... Big Fan❤️
this problem should have been in the hard category instead of medium. but u explained it really well as always. thanks.
This is incredible
simple neat and amazing
I did by using a normal vector for each row I created an adittional 1x9 vector same for each column then I sorted and used std::unique to check for valid rows and columns. Had to use a custom lambda to ignore the "." then for each 3x3 square I created a std::vector sorted each row and used std::unique again. But each the unordered_set approach is better
Surprisingly did this first try, may not have been the best solution but I'm happy I atleast got to A solution lol. I did modulo to figure out when every three in a row and every three rows was. Then I stored values based on the row and subsection in a map with frequency values. Probably didn't need the frequency and could have just set a value now that I'm thinking about it but got to a solution lol.
This was a fun problem!
You are awesome!!
Thank you from Taiwan
I'm not an expert at Big 0 notation, but according to chatGPT `* - The time complexity is O(1). Although we perform nested iterations over the 9x9 board (total 81 cells), this number is constant and independent of the input size.` Kindly correct me if I'm wrong @NeetCode
Thank you, sir :)
Holy shit, I had to use two variables to keep track of the column and rows, then used board[y][(index % 3) + (x % 9)] to advance through the sub-blocks. The simple division by 3 is genius.
What the hell, Initially i thought it is a very tough problem to solve. After your explanation it was a cakewalk. you are very good at this. 👏 and thanks for your videos.
That's why he's the goat.......THE GOAT!!!
Please do more Linked list problems
under loop if you just set temp variable cell = board[r][c] and could use everywhere in conditions and assignments just cell instead of board[r][c] to keep code more clean and less dupes ``` for r in range(9): for c in range(9): cell = board[r][c] if cell == '.': continue if (cell in rows[r] or cell in cols[c] or cell in squares[(r//3, c//3)]): return False cols[c].add(cell) rows[r].add(cell) squares[(r//3, c//3)].add(cell) ```
Thanks !!!
My man recording Leetcode solutions on Fourth of July for us to pass our interviews. What’s your excuse?
can use a single hash map and append the identity [Row/Col/SubBox]
You are good!
great solution
holy shit, this question become so easy!!!! genius
The operations of a HashSet are not O(1), they are O(n). A HashMap has a bound of O(1)
I have an interview in 3 weeks and...how the hell am I supposed to figure this out 😂
It would have probably been a bit easier to understand if you explained the grid position as Blocks in a Chunk, since Minecraft is pretty popular I think it'd be easy for us to relate
Genius solution
you are the goat
Can you please explain the defaultdict part , adn and also how is the rows column and squares are stored inside the dictionary? It's really confusing!
hey it's technically O(1)! thats cool
the (row, col):set() default dictionary is insane
thank you sir
As a (currently) intermediate Python programmer, I can't understand the 2nd line (everything to the right of IsValidSudoku.) Is there a particular concept in Python that explains what you're doing there? (I've covered OOP.) Thanks, love the channel, aiming to soon be good enough to be able to appreciate everything you do here!
@jonaskhanwald566
3 жыл бұрын
If u know oops in python, you will understand that. Those are just arguments, and that bool is the return type of that method
@mousquetaire86
2 жыл бұрын
@jon franklin Ah yes, I've seen it's sometimes called "type hints." Thanks!
@talhakaraca
Жыл бұрын
@@jonfranklin9639 its been a long time but i want to ask a question since you could answer. Why space complexity is O(n^2)? I thought its O(n)
@quanghuyluong1249
Жыл бұрын
@@talhakaraca It's not n square. It is actually n, which is 9 square (4:30)
@talhakaraca
Жыл бұрын
@@quanghuyluong1249 thanks
Actually, there are some firework noises in the background (but my background since I'm watching the video on Diwali in India) :D
can you explain the initialilzations of the sets? can't i just initialize them with : rows= {} ?
The explanation is very good and can be understood easily but I don't know how to code this approach in C++, if some approaches are not possible to code in other languages, suggest what can be in other languages in your upcoming videos :)
@jeffcarey4285
3 жыл бұрын
It's up to you to learn your target language well enough to understand how to adapt explanations. If you insist on using C++ (a bold choice) consider using unordered_set for storing values you've seen. the rest is just loops and array indices.
@suhaasbadada
2 жыл бұрын
i'm quite late but if it helps anyone, this is what i used for cpp unordered_map rows,cols; map squares;
@tsepten7930
2 жыл бұрын
@@suhaasbadada Why do you use map for squares? Why not both unordered_map? I thought unordered_map is better
@farisabufarha531
Жыл бұрын
@@tsepten7930 u can't use pair as a key in unordered_map
How do you get yourself to approach a given problem this way?
This solution is a night mare in java!
The smiley at 7:39 is me
@NeetCode sir please make a video on 37 Leetcode -----> suduko solver... please
@neetcode ... how to come up with own testcases ?
how much time it took to get good level grasp on DSA? when u were able to solve quesitons in half hour