How hard is LeetCode 36. Valid Sudoku?

LeetCode 36. Valid Sudoku is rated Medium on LeetCode.

What is the time complexity of LeetCode 36. Valid Sudoku?

The Python solution on this page runs in O(C).

What is the space complexity of LeetCode 36. Valid Sudoku?

The Python solution on this page uses O(C), where C is the number of empty spaces in the sudoku auxiliary space.

What topics does LeetCode 36. Valid Sudoku cover?

LeetCode 36. Valid Sudoku is tagged Array, Hash Table and Matrix on LeetCode.

Valid Sudoku — LeetCode 36 Python Solution

MediumArrayHash TableMatrix

Problem: #36
Pattern: Matrix and Grid
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

Input: board =
Output: true

Python solution

Python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [[False] * 9 for _ in range(9)]
        col = [[False] * 9 for _ in range(9)]
        sub = [[False] * 9 for _ in range(9)]
        for i in range(9):
            for j in range(9):
                c = board[i][j]
                if c == '.':
                    continue
                num = int(c) - 1
                k = i // 3 * 3 + j // 3
                if row[i][num] or col[j][num] or sub[k][num]:
                    return False
                row[i][num] = True
                col[j][num] = True
                sub[k][num] = True
        return True

Complexity

Measure	Complexity
Time	O(C)
Space	O(C), where C is the number of empty spaces in the sudoku auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 36. Valid Sudoku is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

On study lists

This problem is on NeetCode 150 and Top Interview 150.

Frequently asked questions

How hard is LeetCode 36. Valid Sudoku?: LeetCode 36. Valid Sudoku is rated Medium on LeetCode.
What is the time complexity of LeetCode 36. Valid Sudoku?: The Python solution on this page runs in O(C).
What is the space complexity of LeetCode 36. Valid Sudoku?: The Python solution on this page uses O(C), where C is the number of empty spaces in the sudoku auxiliary space.
What topics does LeetCode 36. Valid Sudoku cover?: LeetCode 36. Valid Sudoku is tagged Array, Hash Table and Matrix on LeetCode.