_36. Valid Sudoku.md

36. Valid Sudoku

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 13, 2024

Last updated : July 04, 2024

---

Related Topics : Array, Hash Table, Matrix

Acceptance Rate : 60.116 %

---

    Ideas
    If we iterate through each row, col, and box, we can do it in O(3n)
    We can have a map for each with the counter of how many of each value
    If the sum of any square > 3 then we return false

---

Solutions

• m36.py

Python

m36.py

# O(3n)

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


        for i in range(len(board)) :
            for j in range(len(board[0])) :
                rows[i][board[i][j]] += 1
                cols[j][board[i][j]] += 1
                threeXthree[self.getNinth(i, j)][board[i][j]] += 1
                
                if board[i][j] != '.' and \
                    rows[i][board[i][j]] + \
                    cols[j][board[i][j]] + \
                    threeXthree[self.getNinth(i, j)][board[i][j]] > 3 :
                    return False
        return True

    def getNinth(self, x: int, y: int) -> int :
        return (3 * (x // 3)) + y // 3