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.

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@ashtag4043]

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🤕

[@jesuscruz8008]

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]

You mean, it's so "neet" ;)

[@dhavallimdiwala]

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

[@parthvalani3273]

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

[@mehdiezatabadi]

This guy is more than just a legend :) He is THE legend!

[@chaitanyasharma6270]

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

[@choiiohc1]

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

[@MP-ny3ep]

This is the best channel in the whole of KZbin🔥

[@Hys-01]

this is the first medium problem that ive done myself which aligns exactly with the optimal solution, i feel accomplished 😅

[@AkshithaKukudala]

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

[@dnguyendev]

The way you explain this problem is brilliant man! So glad I found your channel

[@syafzal273]

The implementation for the squares with floor division and using a tuple as the key is simply amazing!

[@sayaksengupta4335]

This solution is simply beautiful. You have my respect, Neetcode.

[@NeetCode]

Glad it was helpful!

[@ramsesD925]

Mind blown when you said you recorded on 4th of July!! It's been exactly one year! Thanks for everything you do

[@ChanChan-pg4wu]

excellent explanation! Thank you Neetcode!

[@user-wt2jd2qc3m]

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.

[@hunterzhang9489]

This is the definition of NEAT CODE

[@EagerEggplant]

Sets in side of hashes with with the row/column as the key... that's pretty awesome!

[@vamseekotha]

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.

[@tiennguyenthuy7563]

Brilliant answers and explanations. Thank you very much

[@zainrab8629]

Amazing explanation with some really easy and clean code!

[@rahulsbhatt]

Your way of explaining things and implementation is neet. Thanks for posting this!

[@varunajmera]

very well explained and very easy and intuitive

[@Wanderor1]

Amazing! Simply Amazing! Going to join your channel to help support the channel. Keep the videos coming.!

[@aakashgyl]

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.

[@gianniprocida3332]

Excellent explanation for every problem.

[@theartvillebyjessica]

Amazing explanation. Thank you for the wonderful videos.

[@ngndnd]

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

[@dataman4503]

It's actually much easier to call them 3 - NxN matrices instead of 3 hash sets each of size NxN.

[@fahimahyder2394]

Beautifully done

[@Moch117]

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

[@Myshio]

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.

[@gogolaygo1903]

Idk how i'd ever figure this one out without watching a video. As always, thanks!

[@Cocamo1337]

Thank you! Just used this method to solve the problem in C#

[@gurudatt-shahane]

Thanks for making this video. It's a simple and intuitive explanation 🙏

[@c0dertang]

I hard coded the squares XD. This really opened my eyes. Thanks!

[@akagamishanks7991]

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

[@hamzaehsankhan]

This makes my solution look like a crayon drawing of a 2-year-old. Awesome solution and well explained.

[@ruicheng1241]

Thanks So Much For Explanation!

[@aboronilov]

Bro you are awesome. I hope you have a huge salary and you are working on some top IT company!

[@AlexanderKharitonov-cc1ei]

Wonderful explanation! Could you please do 229 Majority Element 2? I am interested in algorithm with O(n) time complexity and O(1) space.

[@the_hasnat]

such an elegant solution. makes it so easy!

[@ThanhPhan-it5gm]

thanks a lot. What you've done is truly delightful

[@gottuparthiharichandana3381]

You are awesome! The code very neat and understandable!! Thanks alot

[@georgeli6820]

great explanation brother!

[@Cruzylife]

preparing for doordash technical rounds, thanks neet

[@uberwebd9824]

very clean and pythonic code

[@MrjavoiThe]

I did a 11 separated for loops solution in Swift, but still get beats 90% in time complexity and 60% in Space complexity.

[@codingtriangle]

Thanks sir...before watching your solution when i solved this question my time complexity was like O(9^4) ....

[@GoziePO]

Funny you recorded this on the 4th of July.! I'm watching it on the 4th of July 2023

[@slava_xd]

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

[@davidbuderim2395]

Thanks - most helpful

[@serhiiDev]

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.

[@arjunprasad1071]

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

[@wildinsights5033]

subscribed and liked, thank you for sharing your knowledge

[@lizgarcia4626]

This is incredible

[@symbol767]

Thanks man, liked

[@shantipriya370]

simple neat and amazing

[@m_elhosseiny]

awesome as usual! :)

[@MrShihab100]

Thanks a lot for your videos :)

[@lifeanddatingadvice1711]

Do sudoku solver next!

[@mingzhejan3906]

Thank you from Taiwan

[@heyasobi]

Can you do LC 1048 Longest String Chain? Watched a few other vids but can't quite wrap my head around it.

[@piyushpawar4815]

You are awesome!!

[@SurfsUpSeth]

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.

[@_dion_]

this problem should have been in the hard category instead of medium. but u explained it really well as always. thanks.

[@rahuljain281]

Please make a video for leetcode 37 Sudoku Solver... Big Fan❤️

[@servantofthelord8147]

Thank you, sir :)

[@sanooosai]

thank you sir

[@brindhadhinakaran9672]

Thanks !!!

[@ljason6361]

great solution

[@diwasmainali1]

Genius solution

[@MK-xl5yo]

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

[@Fauna.Fantastica]

you are the goat

[@servantofthelord8147]

This was a fun problem!

[@amynguy]

can use a single hash map and append the identity [Row/Col/SubBox]

[@lancetv4826]

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

[@aboutvenice]

You are good!

[@jonaskhanwald566]

Please do more Linked list problems

[@mohammadsaudkhan8186]

That's why he's the goat.......THE GOAT!!!

[@sammyapsel1443]

can you explain the initialilzations of the sets? can't i just initialize them with : rows= {} ?

[@cortisol_induced_coma]

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.

[@ThamaraiselvamT]

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.

[@ritwik121]

@neetcode ... how to come up with own testcases ?

[@148nihalmorshed2]

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!

[@kokob5715]

How do you get yourself to approach a given problem this way?

[@naimeimran3247]

Thanks,

[@hwang1607]

the (row, col):set() default dictionary is insane

[@robr4501]

holy shit, this question become so easy!!!! genius

[@amansaxena4446]

how much time it took to get good level grasp on DSA? when u were able to solve quesitons in half hour

[@alittlecoding]

awesome

[@Kitsune_Dev]

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

[@user-fb4iv4me6g]

The operations of a HashSet are not O(1), they are O(n). A HashMap has a bound of O(1)

[@josephjoestar4318]

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.

[@gmoney_swag1274]

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

[@bpsupergirl]

I have an interview in 3 weeks and...how the hell am I supposed to figure this out 😂

[@harishdukkipati8921]

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.

[@NeetCode]

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.

[@harishdukkipati8921]

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

[@jerrykuo8736]

My man recording Leetcode solutions on Fourth of July for us to pass our interviews. What’s your excuse?

[@saurabhchopra]

Assigning board[r][c] to a variable and using the variable instead, makes the runtime of the program almost 2x faster.

[@c0dertang]

hey it's technically O(1)! thats cool

[@chaitanyanimma2939]

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]

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]

i'm quite late but if it helps anyone, this is what i used for cpp unordered_map rows,cols; map squares;

[@tsepten7930]

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