A Python solution - O(n^2) 95ms


  • 3
    G
    class Solution:
        # @param {character[][]} board
        # @return {boolean}
        def isValidSudoku(self, board):
            if not board:
                return False
    
            row, col, box = [[False] * 9 for i in range(10)], [[False] * 9 for i in range(10)], [[False] * 9 for i in range(10)]
    
            for i in range(len(board)):
                for j in range(len(board[0])):
                    num = board[i][j]
                    if num != '.':
                        index = int(num) - 1
                        k = i / 3 * 3 + j / 3
                        if row[i][index] or col[j][index] or box[k][index]:
                            return False
    
                        row[i][index] = col[j][index] = box[k][index] = True
    
            return True

  • 0
    U

    Could you please explain why here we only check row[i][index] col[j][index] and box[k][index] is fine ? why k is equal to i / 3 * 3 + j / 3 ?


  • 0
    G

    row, col, box are flags to check whether a number in a row/col/3x3box has been used before or not. e.g. row[0] represents the boolean flag for each 1-9 number of the first row, namely row[0][0] is boolean flag for 1, row[0][1] is for 2, etc.

    When we iterate through the board, we mark the current number as visited in each row, col, box. So the goal here is, in a valid board, all the numbers of 1-9 should only be used once in each row, col, box. Otherwise the board is invalid.

    As to the i, j - A simple way to make it clear for you is by drawing the board on a paper yourself, and let's say you are given i, j = 2, 3, how do you locate which 3x3box that element belongs to? k = i / 3 * 3 + j / 3 is used to calculate the 3x3box index that element belongs to.


  • 0
    J

    For creating the row, col, box variable, I'm using row=[[False]*9]*9 instead of row=[[False] * 9 for i in range(10)].

    However, in my code the command row[0][0]=True will assign True value for every first element in all 9 list within row variable, while your command only assign True value for the first element in the first list within row variable.

    Could you explain the difference here? Thanks very much!


  • 0
    G

    [[False] * 9] * 9 will create an array of [[False] * 9] and copy it for 9 times by reference, however, [[False] * 9 for i in range(10)] will generate 9 different arrays of [[False] * 9].

    That's why your row[0][0] assignment will be applied to all the 9 arrays (your 9 arrays are technically the same array)


  • 0
    J

    thanks so much for the quick and clear explanation!


  • 0
    J

    when you initialize as [[False] * 9 for i in range(10)] instead of [[False] * 9 for i in range(9)],i think it only needs a 99 matrix instead of a 910 one


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.