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.
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].
Hey bro, do you got any opportunity in maang companies.? In which company are you working at present. I am asking you this because you have started solving problems 3 years ago.
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!!!!!
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!!!
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
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.
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.
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
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
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 a lot @NeetCode for sharing awesome videos on DSA problems 🔥 But In this problem it is mentioned that - Each row must contain the digits 1-9 without duplicates. same for column and squares Based on same if some test cases have digits 9 eg 10, -1 Then seems like the solution suggested in video may get failed. 🤔 Not sure, if the condition checking for the same omitted intentional for simplicity or I'm missing something here. But sharing here, if it helps any future viewers.
If we defined N=9 (and we don't subscribe to the - "it's a defined number so it's constant idea"), you are using N^2 memory here. it could be done with N with three loops (only the current row/col/sqr must be saved). it's at least worth mentioning in an interview. it does make it much more elegant though
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) ```
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.
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
It's only because the probelm itself constraints rows and cols to exactly 9. Hence iterating every row and column would be 9^2, which is a constant of 81. If however, the interviewer did a follow up question such as an "unknown rows and cols at runtime"; the solution would then be n^2.
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.
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.
Hey bro, do you got any opportunity in maang companies.? In which company are you working at present. I am asking you this because you have started solving problems 3 years ago.
Hey bro, do you got any opportunity in maang companies.? In which company are you working at present. I am asking you this because you have started solving problems 3 years ago.
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
Hey bro, do you got any opportunity in maang companies.? In which company are you working at present. I am asking you this because you have started solving problems 3 years ago.
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
You can optimize it more in terms of space. No need for global Dictionary for Rows. Simple Set is fine. It will be destoryed/cleared after the whole row pass (after for-loop with 'c').
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.
"Runtime: 95 ms, faster than 96.98% of Python3 online submissions" and I still came here to watch the video and still learnt things. That is just how good these videos are. Interestingly, checking in order of all rows, all cols, all squares gives the faster time. The test cases much favour some early exits based on 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 :)
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.
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
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!
"Each row MUST contain the digits 1-9 without repetition", "Each column MUST contain the digits 1-9 without repetition", so we could argue that it is also necessary to validate if there is a number that is not in the range 1 to 9...
🚀 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🤕
this is the first medium problem that ive done myself which aligns exactly with the optimal solution, i feel accomplished 😅
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].
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!!
Hey bro, do you got any opportunity in maang companies.? In which company are you working at present. I am asking you this because you have started solving problems 3 years ago.
@@james3677 search up his name on google , I think he works a Deloitte
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!
keys for a dictionary have to be immutable so tuples work
Same man. 2 years as a python developer still this popped
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!!!!!
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!!!
This solution is simply beautiful. You have my respect, Neetcode.
Glad it was helpful!
This is the best channel in the whole of UA-cam🔥
Dude, seriously, this solution was so elegant and brilliant. Thanks, for explaining these things so simply and effectively.
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.
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
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.
Mind blown when you said you recorded on 4th of July!! It's been exactly one year! Thanks for everything you do
The implementation for the squares with floor division and using a tuple as the key is simply amazing!
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.
The way you explain this problem is brilliant man! So glad I found your channel
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
I always fell happy when i got stuck on leetcode problem and you have a video uploaded on it.
this problem should have been in the hard category instead of medium. but u explained it really well as always. thanks.
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
This makes my solution look like a crayon drawing of a 2-year-old. Awesome solution and well explained.
Idk how i'd ever figure this one out without watching a video. As always, thanks!
It's actually much easier to call them 3 - NxN matrices instead of 3 hash sets each of size NxN.
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
This is the definition of NEAT CODE
Funny you recorded this on the 4th of July.! I'm watching it on the 4th of July 2023
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.
preparing for doordash technical rounds, thanks neet
Sets in side of hashes with with the row/column as the key... that's pretty awesome!
Thanks a lot @NeetCode for sharing awesome videos on DSA problems 🔥
But In this problem it is mentioned that
- Each row must contain the digits 1-9 without duplicates.
same for column and squares
Based on same if some test cases have digits 9 eg 10, -1
Then seems like the solution suggested in video may get failed. 🤔
Not sure, if the condition checking for the same omitted intentional for simplicity or I'm missing something here.
But sharing here, if it helps any future viewers.
Thank you! Just used this method to solve the problem in C#
I hard coded the squares XD. This really opened my eyes. Thanks!
If we defined N=9 (and we don't subscribe to the - "it's a defined number so it's constant idea"), you are using N^2 memory here.
it could be done with N with three loops (only the current row/col/sqr must be saved). it's at least worth mentioning in an interview. it does make it much more elegant though
I did a 11 separated for loops solution in Swift, but still get beats 90% in time complexity and 60% in Space complexity.
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)
```
That's why he's the goat.......THE GOAT!!!
Representation in Software Engineer is perhaps the hardest part to get along with. In jobs you definitely don't want to over use it or abstractions.
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
Amazing explanation with some really easy and clean code!
Your way of explaining things and implementation is neet.
Thanks for posting this!
Bro you are awesome. I hope you have a huge salary and you are working on some top IT company!
can use a single hash map and append the identity [Row/Col/SubBox]
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.
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
It's only because the probelm itself constraints rows and cols to exactly 9. Hence iterating every row and column would be 9^2, which is a constant of 81. If however, the interviewer did a follow up question such as an "unknown rows and cols at runtime"; the solution would then be n^2.
Thanks sir...before watching your solution when i solved this question my time complexity was like O(9^4) ....
very well explained and very easy and intuitive
thanks a lot. What you've done is truly delightful
Brilliant answers and explanations. Thank you very much
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.
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.
such an elegant solution. makes it so easy!
My man recording Leetcode solutions on Fourth of July for us to pass our interviews. What’s your excuse?
u made it look so easy
The operations of a HashSet are not O(1), they are O(n). A HashMap has a bound of O(1)
Excellent explanation for every problem.
Thanks for making this video. It's a simple and intuitive explanation 🙏
Amazing! Simply Amazing! Going to join your channel to help support the channel. Keep the videos coming.!
Hey bro, do you got any opportunity in maang companies.? In which company are you working at present. I am asking you this because you have started solving problems 3 years ago.
excellent explanation! Thank you Neetcode!
Hey bro, do you got any opportunity in maang companies.? In which company are you working at present. I am asking you this because you have started solving problems 3 years ago.
Wonderful explanation! Could you please do 229 Majority Element 2? I am interested in algorithm with O(n) time complexity and O(1) space.
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
Do sudoku solver next!
the (row, col):set() default dictionary is insane
Please make a video for leetcode 37 Sudoku Solver... Big Fan❤️
Hey bro, do you got any opportunity in maang companies.? In which company are you working at present. I am asking you this because you have started solving problems 3 years ago.
Thank you from Taiwan
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
Amazing explanation. Thank you for the wonderful videos.
this solution is so simple once you see it
Can you do LC 1048 Longest String Chain? Watched a few other vids but can't quite wrap my head around it.
the squares divided by 3 is insanely smart holy shit
You can optimize it more in terms of space. No need for global Dictionary for Rows. Simple Set is fine. It will be destoryed/cleared after the whole row pass (after for-loop with 'c').
does it matter? the space complexity doesn't even grow with input size.
what is space complexity of this?
This solution is a night mare in java!
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.
Assigning board[r][c] to a variable and using the variable instead, makes the runtime of the program almost 2x faster.
"Runtime: 95 ms, faster than 96.98% of Python3 online submissions" and I still came here to watch the video and still learnt things. That is just how good these videos are.
Interestingly, checking in order of all rows, all cols, all squares gives the faster time. The test cases much favour some early exits based on rows.
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!
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 :)
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.
i'm quite late but if it helps anyone, this is what i used for cpp
unordered_map rows,cols;
map squares;
@@suhaasbadada Why do you use map for squares? Why not both unordered_map? I thought unordered_map is better
@@tsepten7930 u can't use pair as a key in unordered_map
You are awesome!
The code very neat and understandable!!
Thanks alot
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
Hi..can anyone give a bit context on the defaultdict(set) part?
Thanks - most helpful
This is incredible
hey it's technically O(1)! thats cool
Please do more Linked list problems
Genius solution
simple neat and amazing
Thanks So Much For Explanation!
subscribed and liked, thank you for sharing your knowledge
Beautifully done
boolean arrays instead of set would be much efficient
boolean[][] squares = new boolean[9][9];
squares[i / 3 * 3 + j / 3][c]
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!
If u know oops in python, you will understand that. Those are just arguments, and that bool is the return type of that method
@jon franklin Ah yes, I've seen it's sometimes called "type hints." Thanks!
@@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)
@@talhakaraca It's not n square. It is actually n, which is 9 square (4:30)
@@quanghuyluong1249 thanks
"Each row MUST contain the digits 1-9 without repetition", "Each column MUST contain the digits 1-9 without repetition", so we could argue that it is also necessary to validate if there is a number that is not in the range 1 to 9...
Yes, However in the constraint section, they have clearly mentioned this:
board[i][j] is a digit 1-9 or '.'.
thank you sir
very clean and pythonic code
This was a fun problem!
how much time it took to get good level grasp on DSA? when u were able to solve quesitons in half hour
great solution
great explanation brother!