LeetCode 36. Valid Sudoku (Algorithm Explained)

  Рет қаралды 100,751

Nick White

Nick White

Күн бұрын

Пікірлер: 105
@calfland79
@calfland79 4 жыл бұрын
at 9:08 when he said it is not difficult, my face turned into red. If I've never saw this kind of solution before, I would be doomed in a interview :)
@Kitchen-Raccoon4572
@Kitchen-Raccoon4572 4 жыл бұрын
lol he says that for so many problems and I get kinda sad when I hear that :(
@CoolnesXcore
@CoolnesXcore 4 жыл бұрын
@@Kitchen-Raccoon4572 Don't get sad... Nick is a little arrogant plus he has been doing this for a while. Practice makes perfect!
@Turnpost2552
@Turnpost2552 3 жыл бұрын
What most developers mean that it is relatively easy. Like it is relatively easy to get a phd than to become President. Both are exceptionally hard to get though.
@tasneemayham974
@tasneemayham974 Жыл бұрын
For real!!!!! Sheesh I spend 2 hours just to figure out what is happening in my code!!
@impos1ble32
@impos1ble32 4 жыл бұрын
The solution with the single string HashSet looks like pure genius to me. Great video!
@samwilson4597
@samwilson4597 Жыл бұрын
big brain solution
@Ingenius3
@Ingenius3 3 жыл бұрын
Huh, the advantages of knowing your data structures and methods...I've spent 10+ hours on a similar sudoku problem and been trying to use only arrays and 2d arrays combined with control statements, and it's been a nightmare to be honest, and now I see this and I really think I gotta learn some data structures, it's ridiculous how fast you can come up a solution like this
@webknowledge9989
@webknowledge9989 2 жыл бұрын
If you feel bad...don't. He spends a lot of time beforehand looking at different solutions, trying to come up with his own solutions, improve it and improving the different solutions he saw. And then, choosing the best one. This is pure hardwork.
@feeaven
@feeaven 4 ай бұрын
This honestly was the simplest and best solution i've seen.
@shusenacademy
@shusenacademy 4 жыл бұрын
Readable code is much better than smart code. Your solution is understandable. Thanks.
@johnhappy9230
@johnhappy9230 8 ай бұрын
bro you have the best explanation that i've seen. Thank you so much
@pradeepanand5296
@pradeepanand5296 4 жыл бұрын
This is lit. No words. I solved the arcade section of the sudoku by using two hashset one for row and one for column. Never thought this could be the way to optimise the code.
@ruchirai5775
@ruchirai5775 4 жыл бұрын
One word - Genius
@rutustup396
@rutustup396 3 жыл бұрын
The answer were already on leet code. 😅
@sicals1720
@sicals1720 4 жыл бұрын
That moment when he first type the input for strings hash set is just simply mind blowing like "OMG off course it will works"
@Last_Resort991
@Last_Resort991 4 жыл бұрын
It will work better than your grammar teacher.
@a.human.
@a.human. 3 жыл бұрын
@@Last_Resort991 when the grammar nazi doesn't know grammar himself lol
@khanshadab806
@khanshadab806 3 жыл бұрын
Also, you could remove the big 'if' from the 'for' loop and just check if the size of the set is 3*(Number of non-empty places in the board) after the loop. If it is not, the answer is false.
@danieljakel5105
@danieljakel5105 4 жыл бұрын
You could also make a list of 81 list with 9 entries each for every field and number that is possible. Then you write a algorithm that cross out each number from the nine possibilieties that has a double in line, colum or quadrat. When all numbers cut one in a list are crossed out, you have found a new one that you can use to delete the other list of posibilities. If each list have just a number its solved!
@PrinceKumar-el7ob
@PrinceKumar-el7ob 3 жыл бұрын
Exploded my mind what a brilliant way to write aesthetic code man !!
@lugiadark21
@lugiadark21 3 жыл бұрын
This trick is INSANE!!!! I hope I never get asked a problem like this lol
@shubhamkhurana7545
@shubhamkhurana7545 4 жыл бұрын
This was a really cool solution Sir, so we can also implement even a string matching algo using string datatype hash set. This problem really teaches a cool concept!! Thank You Sir!!
@fabusuyiayodeji7016
@fabusuyiayodeji7016 4 жыл бұрын
Wow! This is the most intuitive solution I've seen to this problem
@enthusiasticsimple901
@enthusiasticsimple901 3 жыл бұрын
Great Solution!! Thank Nick for posting these videoss
@aba0101
@aba0101 3 жыл бұрын
Brilliant!! Just to make sure, is the time and space O(1)?
@osamabassam7517
@osamabassam7517 3 жыл бұрын
A clever solution, but the simple solution (Validating rows, columns, and boxes seperately) is way more faster, for me this solution beat 100% of java solution in term of time, the solution in the video beat 22% only (Which is because of strings hashing I guess).
@jordananders8525
@jordananders8525 3 жыл бұрын
Wouldn't this fail if one of the 3x3 squares looks like 1 2 3 4 5 6 7 8 9 and if there is another 3x3 square to the left or the right of the first 3x3 square that looks like 7 4 5 8 2 3 6 1 x where the x denotes an empty square, then this is an unsolvable Sudoku puzzle.
@decisive5760
@decisive5760 2 жыл бұрын
It's doesn't matter if the sudoku puzzle is unsolvable. This leetcode problem is only checking for the three rules in the description
@seyikareem8052
@seyikareem8052 4 жыл бұрын
Curios if it is possible to extend this solution to solve the Sudoku solver problem...
@soumi7356
@soumi7356 3 жыл бұрын
This was a very different approach !
@DeepakAnand-x3f
@DeepakAnand-x3f Жыл бұрын
Rather than using 3 hashsets using a single hashset was brilliant .
@lifeofme3172
@lifeofme3172 2 жыл бұрын
WOW amazing solution loved it keep it up dude!
@Jdudeo
@Jdudeo 4 жыл бұрын
The string concatenation allows using only one map, but what is the point of this? It's nifty, but I don't see a real reason to use this from a practical standpoint
@iamloking
@iamloking 2 жыл бұрын
Loved the solution!
@dangbey4822
@dangbey4822 2 жыл бұрын
genious, thank you very much
@orangetree2104
@orangetree2104 4 жыл бұрын
Trivia : Nick White still has the hat used in his profile picture, and actually went to Columbia
@velmuruganr9321
@velmuruganr9321 3 жыл бұрын
wow..that blew my mind...I mean wow... Im speechless
@emanuelcristutiu5854
@emanuelcristutiu5854 2 жыл бұрын
Really good explanation, thx mate!
@tushar_agarwal_it_2nd_a_477
@tushar_agarwal_it_2nd_a_477 3 жыл бұрын
Can anyone give the cpp solution of this question,I am having some issues in my code.Thanks in advance:)
@suryakumar-ow8bx
@suryakumar-ow8bx Жыл бұрын
its showing unexpected return value for return false line... wat to do
@Nickel80
@Nickel80 4 жыл бұрын
What is the runtime for your solution? Is it O(n^2)?
@praharsh_bhatt
@praharsh_bhatt 4 жыл бұрын
Yes.
@divjyotsinghkhanuja1546
@divjyotsinghkhanuja1546 4 жыл бұрын
It is O(1). The for loop will always run for 9x9 grid irrespective of input if thats how you came up with O(n).
@divjyotsinghkhanuja1546
@divjyotsinghkhanuja1546 4 жыл бұрын
@wapanapoli How can the grid size change lol please explain
@Mark-tv1zs
@Mark-tv1zs Жыл бұрын
@@praharsh_bhatt The grid is always 9x9 (even says in the video), so the time complexity is O(1)
@gopalchavan306
@gopalchavan306 2 жыл бұрын
wow Awesome, and I was spending hours to just solve this
@AbhishekAnand92
@AbhishekAnand92 2 жыл бұрын
Brilliant solutions :D
@vrindatyagi6744
@vrindatyagi6744 4 жыл бұрын
your vids are really helpful THANKS A LOAD
@jz-nz6tq
@jz-nz6tq 4 жыл бұрын
this method is fucking genius
@NikhilTripathy
@NikhilTripathy 4 жыл бұрын
WoW! That's so freaking cool..
@CodeSuccessChronicle
@CodeSuccessChronicle 3 жыл бұрын
Me: (video put on mute until he claps)
@inderjitsaini9303
@inderjitsaini9303 3 жыл бұрын
I tried doing the nested if with normal (seen.add) instead of (!seen.add), return true and return false in outside the for loops. but that doesn't work. Can you tell why?
@vishnudarrshanorp3730
@vishnudarrshanorp3730 Жыл бұрын
in nested if statement you forgot to put ! symbol to check it..
@stutipandey2564
@stutipandey2564 4 жыл бұрын
This is an awesomeeeeeee solution. I am mesmerized!!!! :)
@kulaisaikumarkulai7319
@kulaisaikumarkulai7319 3 жыл бұрын
Great job
@DavisTibbz
@DavisTibbz Жыл бұрын
Really? Snake_case in java? 😅 Anyway, cool content bro
@ServantOfLordKrishna.
@ServantOfLordKrishna. 3 ай бұрын
this makes me look dumb
@SmokyBigSmoke
@SmokyBigSmoke 4 жыл бұрын
Thank you so much
@WowPlusWow
@WowPlusWow 4 жыл бұрын
I did this in c++ and got only 6% faster. You also only got 22% This solution is a joke.
@_sudipidus_
@_sudipidus_ 4 жыл бұрын
Leetcode's system of calculating this is flawed.. I have seen same thing submission showing up as faster than (12%-80%) and then back to 12% within a minute.. (network connection or something)
@sudhanshushakya4579
@sudhanshushakya4579 4 жыл бұрын
Hye, can you show me your cpp implementation? I am having trouble doing it. I used unordered_set in place of HashSet.
@bultvidxxxix9973
@bultvidxxxix9973 4 жыл бұрын
Because this solution is really bad for performance. It's a nice quick solution in a coding interview, but if you want fast execution times, you shouldn't even think about generating strings to hash them... It should more look like this: public boolean isValidSudoku(char[][] board) { for(int i=0; i
@yatinarora1252
@yatinarora1252 3 жыл бұрын
@@sudhanshushakya4579 ya that will be work fine for rows use ur unordered_sename[i].(arr[i][j]and column use ur unordered set name[j].find(arr[i][j]) and array element arr[i][j] and for boads use following as it is 9^9 matrix use arr[i]j].find(arr[i][j]*3(i/3)*(j/3))
@Nathan00at78Uuiu
@Nathan00at78Uuiu 2 жыл бұрын
I'm not understanding the logic and code for specifying a cube. It makes no sense to me.
@decisive5760
@decisive5760 2 жыл бұрын
It's a 9x9 grid. A box is 3x3. If you divide the index of a row and column by 3, you get the box you're currently in.
@MrSharmagaurav03
@MrSharmagaurav03 2 жыл бұрын
This algorithm is wrong as it only check for first subset not all 9 subsets.
@driveb6591
@driveb6591 4 жыл бұрын
Thanks for explaining. What's the time complexity?
@justdevthings.7397
@justdevthings.7397 4 жыл бұрын
O(n*n) where n is the size of the board
@yatinarora1252
@yatinarora1252 3 жыл бұрын
LOL if we used three iterations instead of 1 iteration it will return 95% more faster solutions,in case of 1 iteration in c++ 35% only
@anuraggorkar2299
@anuraggorkar2299 3 жыл бұрын
StefanPochmann sends regards ;)
@arjunsuresh27
@arjunsuresh27 3 жыл бұрын
worst explanation ever!! no intuition or walk through whats so ever cannot explain this in an interview!
@somyasrivastava6315
@somyasrivastava6315 3 жыл бұрын
This is beautiful
@rashedulislam9301
@rashedulislam9301 4 жыл бұрын
nice explanation
@karana2260
@karana2260 4 жыл бұрын
does same number of elements in one hash Set or 3 hash set make a difference on memory usage? after all same units of memory is being allocated but pointers to each memory changes right? the type is same (char)
@thewatcherlollol
@thewatcherlollol 4 жыл бұрын
Well yea, you're using more memory
@shravanipande7990
@shravanipande7990 3 жыл бұрын
Yeah, even I had the same question.
@hopechan697
@hopechan697 4 жыл бұрын
really helpful thanks :3
@swatiswagatika2017
@swatiswagatika2017 2 жыл бұрын
brilliant !!!!
@bobered4911
@bobered4911 Жыл бұрын
Nick no filter white
@roshibansal2095
@roshibansal2095 3 жыл бұрын
You look like sheldon
@pratheek5096
@pratheek5096 4 жыл бұрын
Clever as fuck
@jenblack8065
@jenblack8065 4 жыл бұрын
Explanation according to discussion, no details. Not worth to go through.
@ashwinishanbhogue2917
@ashwinishanbhogue2917 4 жыл бұрын
F R E A K I N G GeniusSSSSSSSSSSS!! :D Mind=blown :)
@amansaxena4446
@amansaxena4446 Жыл бұрын
we dont know what u mean ,
@freesoul2677
@freesoul2677 3 жыл бұрын
It was a nice AHAAAAAAA moment =D Thank you!
@charanpasupula3763
@charanpasupula3763 3 жыл бұрын
Genius
@SudeepDasguptaiginition
@SudeepDasguptaiginition 4 жыл бұрын
excellent !!!!
@algorithmimplementer415
@algorithmimplementer415 4 жыл бұрын
looks like you hate to use camelCase in the camelCase world of Java. :D
@divjyotsinghkhanuja1546
@divjyotsinghkhanuja1546 4 жыл бұрын
He codes in JS except for Data Structures I think thats where the underscores come from ;)
@channelname8300
@channelname8300 4 жыл бұрын
WTF mannnnnnn...........................Destroyed it like a proooooo
@nknidhi321
@nknidhi321 3 жыл бұрын
Mind boggling🔥
@ketansharma6955
@ketansharma6955 Жыл бұрын
nice.
@julietgeorge4858
@julietgeorge4858 4 жыл бұрын
I hope you don't get tired of my comments but this is ridiculous(in a good way )
@demidrek-heyward
@demidrek-heyward 4 жыл бұрын
get it
@YOUNGBLOOD-Alex
@YOUNGBLOOD-Alex 4 жыл бұрын
WTF
@vk1618
@vk1618 4 жыл бұрын
Review
@ankurkoul3731
@ankurkoul3731 3 жыл бұрын
wow :)
@Alison-yg6qs
@Alison-yg6qs 4 жыл бұрын
:-) !!! awesome!!!!!
@ahmedfattah5879
@ahmedfattah5879 4 жыл бұрын
18
@kedikebba6441
@kedikebba6441 4 жыл бұрын
Champ!
@AmanRaj-tj7lj
@AmanRaj-tj7lj 3 жыл бұрын
This does not work. Waste of time
Create a Sudoku Solver In Java In 20 Minutes - Full Tutorial
20:25
Coding with John
Рет қаралды 323 М.
Valid Sudoku - Amazon Interview Question - Leetcode 36 - Python
13:28
CAN YOU DO THIS ?
00:23
STORROR
Рет қаралды 44 МЛН
HELP!!!
00:46
Natan por Aí
Рет қаралды 21 МЛН
REAL 3D brush can draw grass Life Hack #shorts #lifehacks
00:42
MrMaximus
Рет қаралды 12 МЛН
LeetCode 5.  Longest Palindromic Substring (Algorithm Explained)
14:40
Sudoku Solver Leetcode || Example + Code + Explanation
24:57
Code with Alisha
Рет қаралды 9 М.
Valid Sudoku - Leetcode 36 - Hashmaps & Sets (Python)
5:10
Greg Hogg
Рет қаралды 9 М.
Self Taught Programmers... Listen Up.
11:21
Nick White
Рет қаралды 1,1 МЛН
I Got Rejected (again)
9:43
Nick White
Рет қаралды 205 М.
Python Sudoku Solver - Computerphile
10:53
Computerphile
Рет қаралды 1,2 МЛН
Coding Was Hard Until I Learned THESE 5 Things!
8:02
Nick White
Рет қаралды 31 М.
L15. Sudoko Solver | Backtracking
26:10
take U forward
Рет қаралды 282 М.
Pass Your Next Tech Interview With Valid Sudoku
6:42
Chris Courses
Рет қаралды 18 М.
CAN YOU DO THIS ?
00:23
STORROR
Рет қаралды 44 МЛН