Valid Sudoku - Amazon Interview Question - Leetcode 36 - Python
Vložit
- čas přidán 2. 07. 2024
- 🚀 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. - Věda a technologie
🚀 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.
Agreed that is an elegant solution - what I have trouble with is getting to that kind of approach on my own!
@@Flite999 you dont, you pick up patterns and practice similar problems.
@@Flite999 Apart from practice, getting good in maths.
I used "Math.floor(r/ 3) * 3 + Math.floor(c / 3)" to get the index of sub-box
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.
You mean, it's so "neet" ;)
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].
This guy is more than just a legend :) He is THE legend!
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 is the first medium problem that ive done myself which aligns exactly with the optimal solution, i feel accomplished 😅
This solution is simply beautiful. You have my respect, Neetcode.
Glad it was helpful!
I never thought in this question that tuple (r//3, c//3) could be keys for defaultdict. Amazing!
keys for a dictionary have to be immutable so tuples work
Same man. 2 years as a python developer still this popped
This is the best channel in the whole of CZcams🔥
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 implementation for the squares with floor division and using a tuple as the key is simply amazing!
The way you explain this problem is brilliant man! So glad I found your channel
excellent explanation! Thank you Neetcode!
Mind blown when you said you recorded on 4th of July!! It's been exactly one year! Thanks for everything you do
Brilliant answers and explanations. Thank you very much
Amazing explanation with some really easy and clean code!
Your way of explaining things and implementation is neet.
Thanks for posting this!
Amazing! Simply Amazing! Going to join your channel to help support the channel. Keep the videos coming.!
very well explained and very easy and intuitive
Amazing explanation. Thank you for the wonderful videos.
Excellent explanation for every problem.
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
Sets in side of hashes with with the row/column as the key... that's pretty awesome!
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
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.
Beautifully done
thanks a lot. What you've done is truly delightful
I hard coded the squares XD. This really opened my eyes. Thanks!
You are awesome!
The code very neat and understandable!!
Thanks alot
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.
Thank you! Just used this method to solve the problem in C#
Thanks for making this video. It's a simple and intuitive explanation 🙏
Thanks So Much For Explanation!
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
Idk how i'd ever figure this one out without watching a video. As always, thanks!
such an elegant solution. makes it so easy!
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 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.
great explanation brother!
This makes my solution look like a crayon drawing of a 2-year-old. Awesome solution and well explained.
Wonderful explanation! Could you please do 229 Majority Element 2? I am interested in algorithm with O(n) time complexity and O(1) space.
Bro you are awesome. I hope you have a huge salary and you are working on some top IT company!
preparing for doordash technical rounds, thanks neet
very clean and pythonic code
subscribed and liked, thank you for sharing your knowledge
Thanks - most helpful
awesome as usual! :)
Thanks man, liked
This is incredible
simple neat and amazing
I did a 11 separated for loops solution in Swift, but still get beats 90% in time complexity and 60% in Space complexity.
Thanks sir...before watching your solution when i solved this question my time complexity was like O(9^4) ....
Thanks a lot for your videos :)
Funny you recorded this on the 4th of July.! I'm watching it on the 4th of July 2023
It's actually much easier to call them 3 - NxN matrices instead of 3 hash sets each of size NxN.
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.
You are awesome!!
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
Do sudoku solver next!
Thank you from Taiwan
you are the goat
Thanks !!!
thank you sir
great solution
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
Genius solution
Thank you, sir :)
This was a fun problem!
this problem should have been in the hard category instead of medium. but u explained it really well as always. thanks.
You are good!
Please make a video for leetcode 37 Sudoku Solver... Big Fan❤️
Can you do LC 1048 Longest String Chain? Watched a few other vids but can't quite wrap my head around it.
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.
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)
```
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
can use a single hash map and append the identity [Row/Col/SubBox]
That's why he's the goat.......THE GOAT!!!
Please do more Linked list problems
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.
Thanks,
awesome
the (row, col):set() default dictionary is insane
How do you get yourself to approach a given problem this way?
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)
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
understood
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!
You can use a single Set with each number prefixed by {column | row | box}{0...9}{value} ie: 'c08'.
If you think this is or is not as good as neetcodes 3 by 9 sets, explain to me why.
Thanks.
Its not as good as its much less readable - which is important in coding interviews as on of the things they test is your ability to write clean, maintainable code
@neetcode ... how to come up with own testcases ?
The problem mentions that each row, square, and column need to have a digit between 1-9. From the code u have written it returns false if there is any duplicates in the row, square, or column but where exactly does it check that each row, square, and column have a digit from 1-9.
We know that the only values are between 1 and 9. So if there are no duplicates, what other possible value could be there? It's basically pidgen hole principle.
@@NeetCode I forgot only the filled cells need to be validated. I thought the problem required u to make sure there isn't any empty row, column, or square. Thanks for the explanation
hey it's technically O(1)! thats cool
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.
can you explain the initialilzations of the sets?
can't i just initialize them with : rows= {} ?
I have an interview in 3 weeks and...how the hell am I supposed to figure this out 😂
what does it mean by only filled cells need to be validated?
how much time it took to get good level grasp on DSA? when u were able to solve quesitons in half hour
if I just used deaultdict(list) or something, would that be wrong?