if someone doesn't wanna use variable starts, you can modify the for loop like this: for row in range(0,9,3): for col in range(0,9,3): s=set() for i in range(3): for j in range(3): if board[row+i][col+j] in s: return False elif board[row+i][col+j] != '.': s.add(board[row+i][col+j])
I usually solve the problem and then compare to your solution and for the case of the medium difficulty problems, my solution is often somewhat more convoluted than yours; there's always some detail that I miss that makes my solution significantly more complicated. But for once, I am still pretty happy with my solution even after seeing yours! So I felt compelled to share it: class Solution(object): def isValidSudoku(self, board): """ :type board: List[List[str]] :rtype: bool """ sudoku_dict = {} # The format of this dictionary will be number: [{rows},{cols},{box}] for i in range(9): for j in range(9): val = board[i][j] if val == ".": continue box_num = 3 * (i // 3) + (j // 3) if val not in sudoku_dict: sudoku_dict[val] = [{i}, {j}, {box_num}] elif (i in sudoku_dict[val][0]) or (j in sudoku_dict[val][1]) or (box_num in sudoku_dict[val][2]): return False else: sudoku_dict[val][0].add(i) sudoku_dict[val][1].add(j) sudoku_dict[val][2].add(box_num) return True
Hey Greg, thanks for the content. Great solution, although i do wonder, how is it BIG O(1) when we have multiple loops? I'm not the best with the complexity identification.
Thank you! And that's a great question (at any level). Technically, these loops are going to run a constant amount of times (not dependent on the size of the grid) because WE KNOW the grid will be a 9*9. To scan the grid, it takes exactly 81 positions. Not dependent on some N or something. So O(81) is just O(1) in big o talk. I hope this helps!
@@GregHogg ohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh /*click moment*/ Man, I cant rely on explanations all the time, do you have any resources/ or easy tricks to remember this stuff. I've tried a few videos and identifying it kindve goes over my head I get that N^2 (for everytime we do this, run these steps) I also understand O(N), Do this Log N (Half each time, divide and conquer but when the code gets a little longer, kindve difficult to track but yh thanks for getting back :)
Master Data Structures & Algorithms For FREE at AlgoMap.io!
if someone doesn't wanna use variable starts, you can modify the for loop like this:
for row in range(0,9,3):
for col in range(0,9,3):
s=set()
for i in range(3):
for j in range(3):
if board[row+i][col+j] in s:
return False
elif board[row+i][col+j] != '.':
s.add(board[row+i][col+j])
Thanks Greg, you really have a natural talent for teaching. Was struggling with this one
I usually solve the problem and then compare to your solution and for the case of the medium difficulty problems, my solution is often somewhat more convoluted than yours; there's always some detail that I miss that makes my solution significantly more complicated. But for once, I am still pretty happy with my solution even after seeing yours! So I felt compelled to share it:
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
sudoku_dict = {}
# The format of this dictionary will be number: [{rows},{cols},{box}]
for i in range(9):
for j in range(9):
val = board[i][j]
if val == ".":
continue
box_num = 3 * (i // 3) + (j // 3)
if val not in sudoku_dict:
sudoku_dict[val] = [{i}, {j}, {box_num}]
elif (i in sudoku_dict[val][0]) or (j in sudoku_dict[val][1]) or (box_num in sudoku_dict[val][2]):
return False
else:
sudoku_dict[val][0].add(i)
sudoku_dict[val][1].add(j)
sudoku_dict[val][2].add(box_num)
return True
Took me 3 years to understand this question
your explanations are so clear and intuitive, thank you!
Thanks!
Thanks, Greg. This was really helpful!
Glad it was helpful!
Super solution
Helpful content, Keep going
Thanks a ton 😊
greg anna vera level
"Easily the hardest part" lol
super anna
Neat solution
very helpful, thanks!
Glad to hear it!!
Super helpful!!!!!
Awesome 😎😎
Hey Greg, thanks for the content. Great solution, although i do wonder, how is it BIG O(1) when we have multiple loops? I'm not the best with the complexity identification.
Thank you! And that's a great question (at any level). Technically, these loops are going to run a constant amount of times (not dependent on the size of the grid) because WE KNOW the grid will be a 9*9. To scan the grid, it takes exactly 81 positions. Not dependent on some N or something. So O(81) is just O(1) in big o talk. I hope this helps!
@@GregHogg ohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh /*click moment*/
Man, I cant rely on explanations all the time, do you have any resources/ or easy tricks to remember this stuff.
I've tried a few videos and identifying it kindve goes over my head
I get that N^2 (for everytime we do this, run these steps)
I also understand O(N), Do this
Log N (Half each time, divide and conquer
but when the code gets a little longer, kindve difficult to track
but yh thanks for getting back :)
very nice
Why are you not "s.clear()" clearing the set after each check for row, col, and box??
S is being reinitialized at each step. It's not global so it doesn't need to be cleared