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🤕

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

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

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

[@dnguyendev]

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

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

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

[@syafzal273]

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

[@ramsesD925]

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

[@sayaksengupta4335]

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

[@NeetCode]

Glad it was helpful!

[@Wanderor1]

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

[@ChanChan-pg4wu]

excellent explanation! Thank you Neetcode!

[@rahulsbhatt]

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

[@zainrab8629]

Amazing explanation with some really easy and clean code!

[@hunterzhang9489]

This is the definition of NEAT CODE

[@tiennguyenthuy7563]

Brilliant answers and explanations. Thank you very much

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

[@varunajmera]

very well explained and very easy and intuitive

[@gogolaygo1903]

Idk how i'd ever figure this one out without watching a video. As always, 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.

[@theartvillebyjessica]

Amazing explanation. Thank you for the wonderful videos.

[@EagerEggplant]

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

[@c0dertang]

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

[@gianniprocida3332]

Excellent explanation for every problem.

[@gottuparthiharichandana3381]

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

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

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

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

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

[@gurudatt-shahane]

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

[@ThanhPhan-it5gm]

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

[@dataman4503]

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

[@Cocamo1337]

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

[@ruicheng1241]

Thanks So Much For Explanation!

[@fahimahyder2394]

Beautifully done

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

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

[@aboronilov]

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

[@the_hasnat]

such an elegant solution. makes it so easy!

[@GoziePO]

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

[@wildinsights5033]

subscribed and liked, thank you for sharing your knowledge

[@georgeli6820]

great explanation brother!

[@Cruzylife]

preparing for doordash technical rounds, thanks neet

[@uberwebd9824]

very clean and pythonic code

[@heyasobi]

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

[@MrShihab100]

Thanks a lot for your videos :)

[@symbol767]

Thanks man, liked

[@sammyapsel1443]

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

[@lifeanddatingadvice1711]

Do sudoku solver next!

[@MrjavoiThe]

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

[@m_elhosseiny]

awesome as usual! :)

[@kokob5715]

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

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

[@lizgarcia4626]

This is incredible

[@davidbuderim2395]

Thanks - most helpful

[@shantipriya370]

simple neat and amazing

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

[@codingtriangle]

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

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

[@piyushpawar4815]

You are awesome!!

[@muskanmall4401]

if I just used deaultdict(list) or something, would that be wrong?

[@_dion_]

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

[@mingzhejan3906]

Thank you from Taiwan

[@amansaxena4446]

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

[@rahuljain281]

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

[@servantofthelord8147]

This was a fun problem!

[@subhajitnaskar6033]

Hi..can anyone give a bit context on the defaultdict(set) part?

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

[@brindhadhinakaran9672]

Thanks !!!

[@jonaskhanwald566]

Please do more Linked list problems

[@ljason6361]

great solution

[@bonle3771]

what does it mean by only filled cells need to be validated?

[@servantofthelord8147]

Thank you, sir :)

[@diwasmainali1]

Genius solution

[@mohammadsaudkhan8186]

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

[@aboutvenice]

You are good!

[@sanooosai]

thank you sir

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

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

[@Fauna.Fantastica]

you are the goat

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

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

[@robr4501]

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

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

[@hwang1607]

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

[@naimeimran3247]

Thanks,

[@Frets49]

why do we need to use hash set ... when i do the same with a normal dictionary (rows=dict(set()) why does it show key error

[@RenanHiramatsu]

Because you are trying to access key-values in the dictionary that doesn't exist. With a defaultdict once you try to access those that doesn't exist it automatically creates a default value for it, without the keyError.

[@pavan2458]

you can do this instead : rows = {i: set() for i in range(9)} cols = {i: set() for i in range(9)} region = {(i, j): set() for i in range(3) for j in range(3)}

[@amynguy]

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

[@alittlecoding]

awesome

[@alexdeathway]

For some reason, unable to wrap my mind around this completely, how did you come up with using 3*3 block as single block.

[@c0dertang]

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

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

[@mousquetaire86]

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]

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]

@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