Python, short code with explanation, with small space used


  • 1

    This approach uses a single res array and tuples to mark every existing number and its position.
    In stead of using 3 different arrays, only 1 array is used, and if the board is sparse, lots of space could be saved.
    This approach is made by Zach @zqiu01

        res = []
        for row in range(len(board)):
            for col in range(len(board)):
                if board[row][col]=='.': continue
    
                num = board[row][col]
                if (row,'row', num) in res: return False
                else: res.append((row, 'row', num))
    
                if (col,'col',num) in res: return False
                else: res.append((col, 'col', num))
    
                if (row//3, col//3, num) in res: return False
                else: res.append((row//3, col//3,num))
                
        
        return True
    

    '''


  • 0
    A

    @keranchen Not sure how Python actually searches "if ... in ...", but if Python does searching by enumerating every element in the set, then your complexity would be O(n^2), not good.


  • 1

    @ayuanx Agree. But we can change res from list to set. Then the in res is O(1)

    class Solution(object):
        def isValidSudoku(self, board):
            res = set()
            for row in range(len(board)):
                for col in range(len(board)):
                    if board[row][col]=='.': continue
        
                    num = board[row][col]
                    if (row,'row', num) in res: return False
                    else: res.add((row, 'row', num))
        
                    if (col,'col',num) in res: return False
                    else: res.add((col, 'col', num))
        
                    if (row//3, col//3, num) in res: return False
                    else: res.add((row//3, col//3,num))
                    
            return True
    

Log in to reply
 

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