0036.Valid Sudoku

• Link: 36. Valid Sudoku - Medium
• Track: NeetCode150

Question

Restate the problem

• Given a 9x9 board
• Each row must contain the digits 1-9
• Each col must contain the digits 1-9
• Each 3x3 sub-boxes must contain the digits 1-9
• "." is ignored
• Return True when valid

Edge Case

• All ".", return True

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	HashSet	$O(1)$	$O(1)$

Method 1 - HashSet

Approach

• Initial three hash sets, rows, cols, cubes (3x3) set
• Travels every cell (r, c)
  • Skip "."
  • If digit exists in row or col or cube, invalid → return False
  • Otherwise, add it into row, col, cube

Complexity

• Time Complexity: $O(1)$, 9x9 cells
  • Generalized $O(n^2)$
• Space Complexity: $O(1)$
  • Generalized $O(n^2)$

Code

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        cubes = [[set() for _ in range(3)] for _ in range(3)]
 
        for row in range(9):
            for col in range(9):
                val = board[row][col]
 
                if val == ".":
                    continue
 
                if val in rows[row]:
                    return False
                    
                if val in cols[col]:
                    return False
                
                cube_row = row // 3
                cube_col = col // 3
                if val in cubes[cube_row][cube_col]:
                    return False
                
                rows[row].add(val)
                cols[col].add(val)
                cubes[cube_row][cube_col].add(val)
        
        return True

---

Common Mistake

• Initial cube [[set() for _ in range(3)] for _ in range(3)]
• Ignore "."