Problem Statement in English

You’re given a $9x9$ Sudoku board. Determine if it 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 $3x3$ sub-boxes of the grid must contain the digits $1-9$ without repetition.

You only need to validate the filled cells, and the board can be partially filled, where empty cells are represented by the character '.'.

Approach

Since each row, column and box can only contain the digits 1-9 without repetition, we can use three separate data structures to keep track of the numbers we have seen so far in each row, column and box.

If for a certain row or column or box we have already seen a number, we can return false. Otherwise, we can mark the number as seen and continue.

And we’re done!

Solution in Python


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [[False] * 9 for _ in range(9)]
        cols = [[False] * 9 for _ in range(9)]
        boxes = [[False] * 9 for _ in range(9)]

        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = ord(board[i][j]) - ord('1')
                    boxIndex = (i // 3) * 3 + (j // 3)
                    if rows[i][num] or cols[j][num] or boxes[boxIndex][num]:
                        return False
                    rows[i][num] = cols[j][num] = boxes[boxIndex][num] = True
        return True

Complexity

  • Time: $O(1)$
    Since the board size is fixed at $9x9$, the time complexity is constant.

  • Space: $O(1)$
    Since the board size is fixed at $9x9$, the space complexity is constant.

Mistakes I Made

My solution was overcomplicated.

And we are done.