Valid Sudoku

Difficulty: Medium
LeetCode Pattern: Arrays & Hashing

Determine if a 9 x 9 Sudoku board is valid according to the following rules:

1. Each row must contain the digits 1-9 without repetition.

2. Each column must contain the digits 1-9 without repetition.

3. Each of the nine 3 x 3 boxes of the grid must contain the digits 1-9 without repetition.

Note:

• Only the filled cells need to be validated according to the mentioned rules.

• For unfilled cells in the matrix, assume it would be the dot (.) character.

Example 1

• Valid Case.

• It satisfies all properties.

Example 2

• Invalid Case.

• Two 8's in the top left 3x3 box.

• Can the board have all empty cells?

  • Yes, that’s possible.

• Can there by values other than 1-9?

  • No, assume values are 1-9 only.

• Can board size be other than 9x9?

  • No, assume 9x9 board only.

1/ All Checks (Brute Force ⚠️)

• Logic:

  • For each filled cell:

    • Check every value in that row

    • Check every value in that col

    • Check every value in that box

  • If no match → return True

  • If match found → return False

• Big O:

  • Time Complexity: O(n³)

  • Space Complexity: O(1)

2/ Use Multiple Sets (Optimal ✅)

• Logic:

  • Create 27 sets in total:

    • 9 for rows

    • 9 for cols

    • 9 for boxes

  • For each filled cell:

    • Check value in:

      • row set

      • col set

      • box set

    • If value exists → return False

    • Else → add to sets and continue

  • At the end:

    • return True (valid board)

• Big O:

  • Time Complexity: O(n²)

  • Space Complexity: O(1)

• What if the board was nearly empty?

  • Our algorithm still works fine.

  • It will simply skip most cells.

• What if board contains invalid chars?

  • We can add validation checks.

  • If an invalid char is found:

    • Return False (invalid board), or

    • Throw an error (bad input).

• What if the board size was any nxn?

  • Replace hardcoded 9 with n.

  • Box Size is now: sqrt(n) × sqrt(n).

  • Rest of algorithm stays the same.

  • Big O remains the same as well.