Valid Sudoku

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Related Problems
Key Takeaways

📋 Problem Statement

Given a 9x9 board with digits 1-9 and . placeholders, validate that no row, column, or 3x3 sub-box contains duplicate digits.

Example (Valid)


            [["5","3",".",".","7",".",".",".","."], ...]

No conflicts in any row, column, or box.

💡 Key Insights

Each filled cell produces three uniqueness checks (row, col, box).
Box index can be encoded as (r // 3, c // 3).
Skip dots; only validate populated cells.
Fail fast as soon as any duplicate is found.

💻 Solution Approaches

Approach 1: Separate Passes per Row/Column/Box

Time: O(81) | Space: O(9)

Works, but involves repetitive loops and duplicated logic.

Approach 2: Single Pass with 3 Hash Sets (Recommended)

Time: O(81) | Space: O(81)

In practice this is constant for fixed 9x9 boards; in generalized NxN notation it's O(N²).

Python Implementation

          from typing import List


def is_valid_sudoku(board: List[List[str]]) -> bool:
    rows = set()
    cols = set()
    boxes = set()

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

        row_key = (r, value)
        col_key = (c, value)
        box_key = (r // 3, c // 3, value)

        if row_key in rows or col_key in cols or box_key in boxes:
          return False

        rows.add(row_key)
        cols.add(col_key)
        boxes.add(box_key)

    return True
        

JavaScript Implementation

          function isValidSudoku(board) {
  const rows = new Set();
  const cols = new Set();
  const boxes = new Set();

  for (let r = 0; r < 9; r += 1) {
    for (let c = 0; c < 9; c += 1) {
      const value = board[r][c];
      if (value === '.') continue;

      const rowKey = `${r}-${value}`;
      const colKey = `${c}-${value}`;
      const boxKey = `${Math.floor(r / 3)}-${Math.floor(c / 3)}-${value}`;

      if (rows.has(rowKey) || cols.has(colKey) || boxes.has(boxKey)) {
        return false;
      }

      rows.add(rowKey);
      cols.add(colKey);
      boxes.add(boxKey);
    }
  }

  return true;
}
        

🔍 Step-by-Step Walkthrough

Suppose we read cell (0,0)='5'. We add (0,'5'), (0,'5') for column, and (0,0,'5') for box.

Later if another '5' appears in row 0, the row key already exists and we immediately return false.

⚡ Complexity Analysis

Time: O(81) for fixed Sudoku size, or O(N²) for generalized board sizes.

Space: O(81) for stored seen entries (constant in 9x9 case).

🔧 Edge Cases

Empty board of dots only -> valid.
Duplicate in a row with no column conflict yet.
Duplicate in a column with no row conflict yet.
Duplicate only inside one 3x3 box.

🧪 Test Cases

Python

def test_is_valid_sudoku():
    valid_board = [
      ["5","3",".",".","7",".",".",".","."],
      ["6",".",".","1","9","5",".",".","."],
      [".","9","8",".",".",".",".","6","."],
      ["8",".",".",".","6",".",".",".","3"],
      ["4",".",".","8",".","3",".",".","1"],
      ["7",".",".",".","2",".",".",".","6"],
      [".","6",".",".",".",".","2","8","."],
      [".",".",".","4","1","9",".",".","5"],
      [".",".",".",".","8",".",".","7","9"],
    ]

    invalid_row = [row[:] for row in valid_board]
    invalid_row[0][2] = "5"

    assert is_valid_sudoku(valid_board) is True
    assert is_valid_sudoku(invalid_row) is False

    print("all tests passed")

JavaScript

function testIsValidSudoku() {
  const validBoard = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"],
  ];

  const invalidBoard = validBoard.map((row) => [...row]);
  invalidBoard[0][2] = "5";

  console.assert(isValidSudoku(validBoard) === true, "valid board");
  console.assert(isValidSudoku(invalidBoard) === false, "invalid row duplicate");

  console.log("all tests passed");
}

💼 Interview Tips

Clarify this is validation, not solving Sudoku.
Show box-key encoding cleanly and avoid math mistakes.
Discuss constant factors vs generalized complexity.
Return early on first violation for cleaner runtime.

🔗 Related Problems

Sudoku Solver
Valid Anagram (set/map uniqueness checks)
N-Queens constraint tracking

🎓 Key Takeaways

Each filled cell implies exactly three uniqueness constraints.
Composite keys make duplicate detection straightforward.
Sudoku validation is a clean example of constraint-system design.