LeetCode 36: Valid Sudoku

Problem Description

Difficulty: Medium

You are given a a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:

• Each row must contain the digits 1-9 without duplicates.
• Each column must contain the digits 1-9 without duplicates.
• Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.

Return true if the Sudoku board is valid, otherwise return false

Note: A board does not need to be full or be solvable to be valid.

Examples are provided in the code below.

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.

Initial Solution

Oh, man. This will involve a few loops and a lot of conditional statements. There is probably a neat mathematical trick but I’d rather not spend the time trying to figure it out. Let’s brute force the problem…

from typing import List
from collections import defaultdict

board1 = [["1","2",".",".","3",".",".",".","."],
          ["4",".",".","5",".",".",".",".","."],
          [".","9","8",".",".",".",".",".","3"],
          ["5",".",".",".","6",".",".",".","4"],
          [".",".",".","8",".","3",".",".","5"],
          ["7",".",".",".","2",".",".",".","6"],
          [".",".",".",".",".",".","2",".","."],
          [".",".",".","4","1","9",".",".","8"],
          [".",".",".",".","8",".",".","7","9"]]

# Output: True

board2 = [["1","2",".",".","3",".",".",".","."],
          ["4",".",".","5",".",".",".",".","."],
          [".","9","1",".",".",".",".",".","3"],
          ["5",".",".",".","6",".",".",".","4"],
          [".",".",".","8",".","3",".",".","5"],
          ["7",".",".",".","2",".",".",".","6"],
          [".",".",".",".",".",".","2",".","."],
          [".",".",".","4","1","9",".",".","8"],
          [".",".",".",".","8",".",".","7","9"]]

# Output: False (two 1's in the top left 3x3 box)

board3 = [["1","2",".",".","3",".",".",".","."],
          ["4",".",".","5",".",".",".",".","."],
          [".","9","1",".",".",".",".",".","3"],
          ["5",".","1",".","6",".",".",".","4"],
          [".",".",".","8",".","3",".",".","5"],
          ["7",".",".",".","2",".",".",".","6"],
          [".",".",".",".",".",".","2",".","."],
          [".",".",".","4","1","9",".",".","8"],
          [".",".",".",".","8",".",".","7","9"]]

# Output: False (two 1's in column 2)

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:

        row_dict = defaultdict(list)
        columns = defaultdict(list)
        box = defaultdict(list)

        for i, row in enumerate(board):        
            for j, value in enumerate(row):
                # ignore dots       
                if value == '.':
                    continue
                # check if seen in a row before
                if value in row_dict[i]: return False
                row_dict[i].append(value)

                # create columns and check if valid
                if value in columns[j]: return False
                columns[j].append(value)

                # create 3x3 boxes and check if valid
                if i < 3:
                    if j < 3:
                        if value in box[0]: return False
                        box[0].append(value)
                    elif j < 6:
                        if value in box[1]: return False
                        box[1].append(value)
                    else:
                        if value in box[2]: return False
                        box[2].append(value)
                elif i < 6:
                    if j < 3:
                        if value in box[3]: return False
                        box[3].append(value)
                    elif j < 6:
                        if value in box[4]: return False
                        box[4].append(value)
                    else:
                        if value in box[5]: return False
                        box[5].append(value)
                else:
                    if j < 3:
                        if value in box[6]: return False
                        box[6].append(value)
                    elif j < 6:
                        if value in box[7]: return False
                        box[7].append(value)
                    else:
                        if value in box[8]: return False
                        box[8].append(value)
        return True

boards = [board1, board2, board3]
expected = [True, False, False]
solution = Solution()

# Get results
results = [solution.isValidSudoku(board) for board in boards]

# Compare results with expected values
if results == expected:
    print("Tests passed")
else:
    print("Tests failed")
    print("Expected:", expected)
    print("Got:", results)

Tests passed

Summary

• Time Complexity: \(O(1)\) as the operations are bounded by a fixed number of iterations and checks in a 9x9 Sudoku board (specifically, 81 operations). If the size of the board were variable, the complexity would be \(O(n^2)\) due to the nested loop.
• Space Complexity: \(O(1)\) as the space used by the defaultdicts is also bounded by the fixed number of entries in the 9x9 board (specifically, 3 dictionaries each holding up to 81 entries in total).

NeetCode Solution

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = defaultdict(set)
        rows = defaultdict(set)
        squares = defaultdict(set)  # key = (r /3, c /3)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if (
                    board[r][c] in rows[r]
                    or board[r][c] in cols[c]
                    or board[r][c] in squares[(r // 3, c // 3)]
                ):
                    return False
                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])

        return True

Conclusion

NeetCode’s solution is a lot cleaner but is essentially the same approach. However, it does use a neat trick of integer division to compute the 3x3 grids. It also uses defaultdict(set) instead defaultdict(list) which will improve the efficiency of the lookup operations.