36. Valid Sudoku (Medium)

Problem

Determine whether a 9×9 Sudoku board is valid (note: not necessarily solvable; just that the current filled cells don’t violate any rules):

Each row contains the digits 1-9 without repetition.
Each column contains the digits 1-9 without repetition.
Each of the nine 3×3 sub-boxes contains the digits 1-9 without repetition.

Empty cells are '.'.

LeetCode 36 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, three separate passes

Check rows, then columns, then boxes, each with a fresh set.

def is_valid_sudoku(board: list[list[str]]) -> bool:
    # Rows
    for row in board:                          # L1: 9 rows
        seen = set()                           # L2: O(1) fresh set
        for ch in row:                         # L3: 9 chars per row
            if ch == '.':                      # L4: O(1) skip
                continue
            if ch in seen:                     # L5: O(1) set lookup
                return False
            seen.add(ch)                       # L6: O(1) set insert

    # Columns
    for c in range(9):                         # L7: 9 columns
        seen = set()
        for r in range(9):                     # L8: 9 rows per column
            ch = board[r][c]
            if ch == '.':
                continue
            if ch in seen:
                return False
            seen.add(ch)

    # 3x3 boxes
    for br in range(0, 9, 3):                  # L9: 3 box-row offsets
        for bc in range(0, 9, 3):              # L10: 3 box-col offsets
            seen = set()
            for r in range(br, br + 3):        # L11: 3 rows per box
                for c in range(bc, bc + 3):    # L12: 3 cols per box
                    ch = board[r][c]
                    if ch == '.':
                        continue
                    if ch in seen:
                        return False
                    seen.add(ch)
    return True

function isValidSudoku(board: string[][]): boolean {
    // Rows
    for (const row of board) {                         // L1: 9 rows
        const seen = new Set<string>();                // L2: fresh set
        for (const ch of row) {                        // L3: 9 chars per row
            if (ch === '.') continue;                  // L4: skip
            if (seen.has(ch)) return false;            // L5: set lookup
            seen.add(ch);                              // L6: set insert
        }
    }
    // Columns
    for (let c = 0; c < 9; c++) {                      // L7: 9 columns
        const seen = new Set<string>();
        for (let r = 0; r < 9; r++) {                  // L8: 9 rows per column
            const ch = board[r][c];
            if (ch === '.') continue;
            if (seen.has(ch)) return false;
            seen.add(ch);
        }
    }
    // 3x3 boxes
    for (let br = 0; br < 9; br += 3) {                // L9: 3 box-row offsets
        for (let bc = 0; bc < 9; bc += 3) {            // L10: 3 box-col offsets
            const seen = new Set<string>();
            for (let r = br; r < br + 3; r++) {        // L11: 3 rows per box
                for (let c = bc; c < bc + 3; c++) {    // L12: 3 cols per box
                    const ch = board[r][c];
                    if (ch === '.') continue;
                    if (seen.has(ch)) return false;
                    seen.add(ch);
                }
            }
        }
    }
    return true;
}

func isValidSudoku(board [][]byte) bool {
  // Rows
  for r := 0; r < 9; r++ {                          // L1: 9 rows
    seen := make(map[byte]struct{})                // L2: fresh set
    for c := 0; c < 9; c++ {                      // L3: 9 chars per row
      ch := board[r][c]
      if ch == '.' { continue }                  // L4: skip
      if _, ok := seen[ch]; ok { return false }  // L5: set lookup
      seen[ch] = struct{}{}                      // L6: set insert
    }
  }
  // Columns
  for c := 0; c < 9; c++ {                          // L7: 9 columns
    seen := make(map[byte]struct{})
    for r := 0; r < 9; r++ {                      // L8: 9 rows per column
      ch := board[r][c]
      if ch == '.' { continue }
      if _, ok := seen[ch]; ok { return false }
      seen[ch] = struct{}{}
    }
  }
  // 3x3 boxes
  for br := 0; br < 9; br += 3 {                    // L9: 3 box-row offsets
    for bc := 0; bc < 9; bc += 3 {                // L10: 3 box-col offsets
      seen := make(map[byte]struct{})
      for r := br; r < br+3; r++ {              // L11: 3 rows per box
        for c := bc; c < bc+3; c++ {          // L12: 3 cols per box
          ch := board[r][c]
          if ch == '.' { continue }
          if _, ok := seen[ch]; ok { return false }
          seen[ch] = struct{}{}
        }
      }
    }
  }
  return true
}

Where the time goes, line by line

Variables: board is always 9×9, so all sizes are constant; no variable-size inputs.

Line	Per-call cost	Times executed	Contribution
L1-L6 (row pass)	$O(1)$ per cell	81 cells	$O(81)$ = $O(1)$
L7-L8 (column pass)	$O(1)$ per cell	81 cells	$O(81)$ = $O(1)$
L9-L12 (box pass)	$O(1)$ per cell	81 cells	$O(81)$ = $O(1)$ ← same

All three passes together visit 81 cells three times each. The board is fixed-size, so every loop is bounded by a constant.

Complexity

Time: $O(81)$ = $O(1)$ , driven by three constant-bounded passes over the 81-cell board.
Space: $O(9)$ = $O(1)$ for each set.

Works, but reads the board three times. The larger Big-O lesson: a “constant-sized” input has $O(1)$ time regardless of method; the engineering question is clarity.

Swift

final class Solution {
    func isValidSudoku(_ board: [[String]]) -> Bool {
        for row in 0..<9 {
            var seen = Set<String>()
            for col in 0..<9 where board[row][col] != "." { if !seen.insert(board[row][col]).inserted { return false } }
        }
        for col in 0..<9 {
            var seen = Set<String>()
            for row in 0..<9 where board[row][col] != "." { if !seen.insert(board[row][col]).inserted { return false } }
        }
        for boxRow in stride(from: 0, to: 9, by: 3) {
            for boxCol in stride(from: 0, to: 9, by: 3) {
                var seen = Set<String>()
                for row in boxRow..<(boxRow + 3) { for col in boxCol..<(boxCol + 3) where board[row][col] != "." {
                    if !seen.insert(board[row][col]).inserted { return false }
                }}
            }
        }
        return true
    }
}

Approach 2: Single pass with nine sets per dimension

Maintain 9 row-sets, 9 column-sets, and 9 box-sets; one pass over the board.

def is_valid_sudoku(board: list[list[str]]) -> bool:
    rows = [set() for _ in range(9)]           # L1: O(1), 9 empty sets
    cols = [set() for _ in range(9)]           # L2: O(1)
    boxes = [set() for _ in range(9)]          # L3: O(1)

    for r in range(9):                         # L4: 9 rows
        for c in range(9):                     # L5: 9 cols each
            ch = board[r][c]                   # L6: O(1) array access
            if ch == '.':                      # L7: O(1) skip
                continue
            b = (r // 3) * 3 + (c // 3)       # L8: O(1) box index
            if ch in rows[r] or ch in cols[c] or ch in boxes[b]:  # L9: O(1) x3 lookups
                return False
            rows[r].add(ch)                    # L10: O(1)
            cols[c].add(ch)                    # L11: O(1)
            boxes[b].add(ch)                   # L12: O(1)
    return True

function isValidSudoku(board: string[][]): boolean {
    const rows = Array.from({length: 9}, () => new Set<string>());   // L1
    const cols = Array.from({length: 9}, () => new Set<string>());   // L2
    const boxes = Array.from({length: 9}, () => new Set<string>());  // L3

    for (let r = 0; r < 9; r++) {                                     // L4: 9 rows
        for (let c = 0; c < 9; c++) {                                 // L5: 9 cols each
            const ch = board[r][c];                                   // L6: O(1)
            if (ch === '.') continue;                                  // L7: skip
            const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);    // L8: O(1) box index
            if (rows[r].has(ch) || cols[c].has(ch) || boxes[b].has(ch)) // L9: O(1)
                return false;
            rows[r].add(ch);                                          // L10
            cols[c].add(ch);                                          // L11
            boxes[b].add(ch);                                         // L12
        }
    }
    return true;
}

func isValidSudoku(board [][]byte) bool {
  rows := make([]map[byte]struct{}, 9)
  cols := make([]map[byte]struct{}, 9)
  boxes := make([]map[byte]struct{}, 9)
  for i := 0; i < 9; i++ {
    rows[i] = make(map[byte]struct{})   // L1: O(1), 9 empty maps
    cols[i] = make(map[byte]struct{})   // L2: O(1)
    boxes[i] = make(map[byte]struct{})  // L3: O(1)
  }
  for r := 0; r < 9; r++ {                              // L4: 9 rows
    for c := 0; c < 9; c++ {                          // L5: 9 cols each
      ch := board[r][c]                              // L6: O(1)
      if ch == '.' { continue }                      // L7: skip
      b := (r/3)*3 + (c / 3)                        // L8: O(1) box index
      _, inRow := rows[r][ch]
      _, inCol := cols[c][ch]
      _, inBox := boxes[b][ch]
      if inRow || inCol || inBox { return false }    // L9: O(1) x3 lookups
      rows[r][ch] = struct{}{}                       // L10
      cols[c][ch] = struct{}{}                       // L11
      boxes[b][ch] = struct{}{}                      // L12
    }
  }
  return true
}

Where the time goes, line by line

Variables: board is always 9×9, so all sizes are constant; no variable-size inputs.

Line	Per-call cost	Times executed	Contribution
L1-L3 (init sets)	$O(1)$	1	$O(1)$
L4-L5 (double loop)	$O(1)$	81	$O(1)$
L6-L12 (per-cell work)	$O(1)$	81	$O(1)$ ← dominates

One pass, constant work per cell, short-circuits on the first conflict.

Complexity

Time: $O(81)$ = $O(1)$ , driven by the single 81-cell pass (L4/L5 with L6-L12).
Space: $O(81)$ = $O(1)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func isValidSudoku(_ board: [[String]]) -> Bool {
        var rows = Array(repeating: Set<String>(), count: 9)
        var columns = Array(repeating: Set<String>(), count: 9)
        var boxes = Array(repeating: Set<String>(), count: 9)
        for row in 0..<9 { for col in 0..<9 {
            let value = board[row][col]
            if value == "." { continue }
            let box = (row / 3) * 3 + col / 3
            guard rows[row].insert(value).inserted, columns[col].insert(value).inserted, boxes[box].insert(value).inserted else { return false }
        }}
        return true
    }
}

Approach 3: Bitmask-based single pass (optimal constant factors)

Replace each set with a 9-bit integer. Bit i is set if digit i+1 is already present.

def is_valid_sudoku(board: list[list[str]]) -> bool:
    rows = [0] * 9                             # L1: O(1), 9 integers
    cols = [0] * 9                             # L2: O(1)
    boxes = [0] * 9                            # L3: O(1)

    for r in range(9):                         # L4: 9 rows
        for c in range(9):                     # L5: 9 cols each
            ch = board[r][c]                   # L6: O(1)
            if ch == '.':                      # L7: skip
                continue
            bit = 1 << (int(ch) - 1)          # L8: O(1) bitmask
            b = (r // 3) * 3 + (c // 3)       # L9: O(1) box index
            if rows[r] & bit or cols[c] & bit or boxes[b] & bit:  # L10: O(1) x3 AND
                return False
            rows[r] |= bit                     # L11: O(1) OR
            cols[c] |= bit                     # L12: O(1)
            boxes[b] |= bit                    # L13: O(1)
    return True

function isValidSudoku(board: string[][]): boolean {
    const rows = new Array(9).fill(0);                              // L1
    const cols = new Array(9).fill(0);                              // L2
    const boxes = new Array(9).fill(0);                             // L3

    for (let r = 0; r < 9; r++) {                                   // L4: 9 rows
        for (let c = 0; c < 9; c++) {                               // L5: 9 cols each
            const ch = board[r][c];                                 // L6
            if (ch === '.') continue;                                // L7: skip
            const bit = 1 << (parseInt(ch) - 1);                   // L8: O(1) bitmask
            const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);  // L9: O(1) box index
            if (rows[r] & bit || cols[c] & bit || boxes[b] & bit)  // L10: O(1) AND
                return false;
            rows[r] |= bit;                                         // L11
            cols[c] |= bit;                                         // L12
            boxes[b] |= bit;                                        // L13
        }
    }
    return true;
}

func isValidSudoku(board [][]byte) bool {
  var rows, cols, boxes [9]int               // L1-L3: O(1), 9 integers each
  for r := 0; r < 9; r++ {                  // L4: 9 rows
    for c := 0; c < 9; c++ {              // L5: 9 cols each
      ch := board[r][c]                  // L6
      if ch == '.' { continue }          // L7: skip
      bit := 1 << (ch - '1')            // L8: O(1) bitmask
      b := (r/3)*3 + (c / 3)            // L9: O(1) box index
      if rows[r]&bit != 0 || cols[c]&bit != 0 || boxes[b]&bit != 0 {
        return false                   // L10: O(1) AND
      }
      rows[r] |= bit                     // L11
      cols[c] |= bit                     // L12
      boxes[b] |= bit                    // L13
    }
  }
  return true
}

Where the time goes, line by line

Variables: board is always 9×9, so all sizes are constant; no variable-size inputs.

Line	Per-call cost	Times executed	Contribution
L1-L3 (init arrays)	$O(1)$	1	$O(1)$
L4-L5 (double loop)	$O(1)$	81	$O(1)$
L6-L13 (per-cell bitmask ops)	$O(1)$	81	$O(1)$ ← dominates

Integer bit operations (&, |, <<) are faster than hash-set operations at the hardware level, but both are $O(1)$ per cell in Big-O terms.

Complexity

Time: $O(1)$ . Same as the hash-set version but with constant-factor gains from integer bit ops vs. set ops.
Space: $O(1)$ . 27 integers vs. 27 sets of up to 9 strings.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func isValidSudoku(_ board: [[String]]) -> Bool {
        var rows = Array(repeating: 0, count: 9), columns = rows, boxes = rows
        for row in 0..<9 { for col in 0..<9 {
            let value = board[row][col]
            if value == "." { continue }
            let bit = 1 << (Int(value)! - 1), box = (row / 3) * 3 + col / 3
            if rows[row] & bit != 0 || columns[col] & bit != 0 || boxes[box] & bit != 0 { return false }
            rows[row] |= bit; columns[col] |= bit; boxes[box] |= bit
        }}
        return true
    }
}

Summary

Approach	Time	Space	Notes
3 separate passes	$O(1)$	$O(1)$	Easiest to read
Single pass, 27 sets	$O(1)$	$O(1)$	Short-circuit on first conflict
Single pass, bitmasks	$O(1)$	$O(1)$	Fastest constant factor

All approaches are formally $O(1)$ because the board is fixed-size; the differences are clarity and constant-factor speed. The bitmask version is the classic “good-enough-for-interview” flex.

# Quick smoke tests, paste into a REPL or save as test_valid_sudoku.py and run.
# Uses the canonical implementation (Approach 3: bitmask single pass).

def is_valid_sudoku(board: list[list[str]]) -> bool:
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            bit = 1 << (int(ch) - 1)
            b = (r // 3) * 3 + (c // 3)
            if rows[r] & bit or cols[c] & bit or boxes[b] & bit:
                return False
            rows[r] |= bit
            cols[c] |= bit
            boxes[b] |= bit
    return True

def _run_tests():
    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"]
    ]
    assert is_valid_sudoku(valid_board) == True

    # Duplicate in a row
    dup_row = [
        ["8","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"]
    ]
    assert is_valid_sudoku(dup_row) == False

    # All dots (empty board) is valid
    empty = [["."]*9 for _ in range(9)]
    assert is_valid_sudoku(empty) == True

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function isValidSudoku(board: string[][]): boolean {
    const rows = new Array(9).fill(0);
    const cols = new Array(9).fill(0);
    const boxes = new Array(9).fill(0);
    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            const ch = board[r][c];
            if (ch === '.') continue;
            const bit = 1 << (parseInt(ch) - 1);
            const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
            if (rows[r] & bit || cols[c] & bit || boxes[b] & bit) return false;
            rows[r] |= bit;
            cols[c] |= bit;
            boxes[b] |= bit;
        }
    }
    return true;
}

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"]
];
console.assert(isValidSudoku(validBoard) === true);
const dupRow = [
    ["8","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"]
];
console.assert(isValidSudoku(dupRow) === false);
const empty: string[][] = Array.from({length: 9}, () => Array(9).fill('.'));
console.assert(isValidSudoku(empty) === true);
console.log("all tests pass");

Arrays, the 9×9 board; indexing arithmetic for the box number
Hash Tables, per-row/col/box membership sets

Constraint Search, the pruning model for choices that must satisfy local and global rules.
Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.

36. Valid Sudoku (Medium)

Problem

Try it yourself

Approach 1: Brute force, three separate passes

Approach 2: Single pass with nine sets per dimension

Approach 3: Bitmask-based single pass (optimal constant factors)

Summary

Test cases

Related data structures

Related concepts