Valid Sudoku

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given an array of arrays representing a sudoku board
• Return True if the sudoku board is valid else False

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Each row can have 1 to 9
• Each col can have 1 to 9
• Each board can have 1 to 9

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• For each row, col and board maintain a set
• Return False if number already exists in the set

Why This Works

(Explain the core reason the solution is correct.)

• Set allows $O(1)$ lookup whether a number exists already
• For each row, col and board we can maintain a set

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Sets
• Array

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through each element just once
• Space: $O(1)$ → Reason: Storing 1-9 digits (27 times max)

Code

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        box = [[set() for j in range(3)] for i in range(3)]

        for r in range(9):
            for c in range(9):
                cell = board[r][c]
                if cell == ".":
                    continue

                if cell in rows[r] or cell in cols[c] or cell in box[r // 3][c // 3]:
                    return False

                rows[r].add(cell)
                cols[c].add(cell)
                box[r // 3][c // 3].add(cell)
        return True

Common Mistakes / Things I Got Stuck On

• How to build a list of lists to represent boxes box = [[set() for j in range(3)] for i in range(3)]
• How to maintain the box

if cell in box[r // 3][c // 3]:
	return False
# 0//3 = 0
# 2//3 = 0
# 3//3 = 1
# 5//3 = 1
# 6//3 = 2
# 8//3 = 2