Problem Description

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:

36.ValidSudoku.png

  • 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.

My Idea

The approach here was to iterate over the input only once. For each non-empty cell board[i][j] we create 3 tuples:

  • (i,board[i][j]) representing (row, element)
  • (board[i][j],j) representing (element, column)
  • (board[i][j],quadrant[x],quadrant[y]) representing (element, quadrant(x), quadrant(y)) The position of element in the first two tuples is different on purpose, so that the entries for row and column are unique( keeping in mind that row and column are int and element is str). Once we have traversed all elements we convert the list of tuples to a set and compare the length of the set to the one of the list. If the length changed that means the list contained duplicates, meaning that one of the 3 rules was broken, which invalidates the sudoku.

My solution

# Technicaly O(1) time, but since it only traverses the input once
#and does one conversion it can be seen as O(n) time complexity.
def isValidSudoku(board: list[list[str]]) -> bool:
    positions=[]
    quadrant=[1,1,1,2,2,2,3,3,3]
    x=-1
    y=-1
    for i in range(0,9):
        x+=1
        y=-1
        for j in range(0,9):
            y+=1
            if board[i][j] != '.':
                positions.append((i,board[i][j]))
                positions.append((board[i][j],j))
                positions.append((board[i][j],quadrant[x],quadrant[y]))
    return len(positions)==len(set(positions))