Leetcode - 36. Valid Sudoku

Medium

Dec 22, 2025

#matrix

36. Valid Sudoku

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

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
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.

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

Constraints:

Notes

Intuition

A valid Sudoku has no duplicates in any row, column, or 3×3 subbox. We need to verify all three constraints independently.

Implementation

Use hashmaps to track seen values. First, iterate through each row checking for duplicates. Then iterate through each column. Finally, check each of the nine 3×3 subboxes. Skip empty cells (".") during all checks.

Edge-cases

The 3×3 subbox indexing is tricky. Use four nested loops: box_row (0-2), box_col (0-2), row (0-2), col (0-2). Access cells with board[3 * box_row + row][3 * box_col + col].

Time: O(1) — board is always 9×9, so effectively constant
Space: O(1) — hashmaps hold at most 9 elements each

Complexity

Solution

from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:

        # Check rows
        for row in range(len(board)):
            map = {}
            for col in range(len(board[row])):
                if board[row][col] == ".":
                    continue
                if board[row][col] in map:
                    return False
                map[board[row][col]] = True

        # Check cols
        for col in range(len(board)):
            map = {}
            for row in range(len(board[col])):
                if board[row][col] == ".":
                    continue
                if board[row][col] in map:
                    return False
                map[board[row][col]] = True

        # Check sub boxes
        for brow in range(3):
            for bcol in range(3):
                map = {}
                for row in range(3):
                    for col in range(3):
                        if board[3 * brow + row][3 * bcol + col] == ".":
                            continue
                        if board[3 * brow + row][3 * bcol + col] in map:
                            return False
                        map[board[3 * brow + row][3 * bcol + col]] = True
        return True
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()