LC 36 - Valid Sudoku

Question

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false

Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid.

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

Links

Question here and solution here

Solution

concept

We mainly iterate through all the cells to check if there is a duplicate in number 1-9. The smart thing in NeetCode solution is to use r//3, c//3 to keep track the small subsqures.

code

class MySolution:
	"""
	brute force to check all cells
	"""
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        ROW = len(board)
        COL = len(board[0])
        
        # check every row
        for r in range(ROW):
            num_set = set()
            for c in range(COL):
                if board[r][c] != "." and board[r][c] in num_set:
                    return False
                num_set.add(board[r][c]) # will add "." also but it's ok

        # check every col
        for c in range(COL):
            num_set = set()
            for r in range(ROW):
                if board[r][c] != "." and board[r][c] in num_set:
                    return False
                num_set.add(board[r][c]) # will add "." also but it's ok

        # check squre
        group = [[0,1,2], [3,4,5], [6,7,8]]
        for r_group in group:
            for c_group in group:
                num_set = set()
                for r in r_group:
                    for c in c_group:
                        if board[r][c] != "." and board[r][c] in num_set:
                            return False
                        num_set.add(board[r][c]) # will add "." also but it's ok

        return True

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool

        time complexity: O(9^2)
        space complexity: O(9^2)
        stored the filled numbers in each row, col, and box hashset
        for boxes, we use (r//3, c//3) as the key so that we reduce from 81*81 -> 3*3 grid to identify the box
        """
        row_set = defaultdict(set) # key: r
        col_set = defaultdict(set) # key: c
        box_set = defaultdict(set) # key: (r//3, c//3), val: set for number 1-9

        for r in range(9): #row
            for c in range(9): #col
                if board[r][c] == ".":
                    continue
                if board[r][c] in row_set[r] or board[r][c] in col_set[c] or board[r][c] in box_set[(r//3,c//3)]:
                    return False
                row_set[r].add(board[r][c])
                col_set[c].add(board[r][c])
                box_set[(r//3,c//3)].add(board[r][c])
    
        return True

Complexity

time: $O(n^2)$
space: $O(n^2)$