Problem statement

Determine whether a 9 × 9 Sudoku board is valid. Only the filled cells need to be checked, according to three 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 × 3 sub-boxes must contain the digits 1-9 without repetition.

Empty cells are represented by 0. A valid board is not necessarily solvable — only the currently filled cells matter.

Example 1

Input: board = [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]
Output: true

Example 2

Input: board = [[8,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]
Output: false
Explanation: Two 8s share the top-left 3 × 3 box.

Example 3

Input: board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
Output: true
Explanation: An empty board breaks no rule.

Constraints

• board.length == 9
• board[i].length == 9
• 0 <= board[i][j] <= 9, where 0 means empty.

Hints for Valid Sudoku

1. Hint 1

   Keep nine sets for the rows, nine for the columns and nine for the boxes.

2. Hint 2

   The box index of (r, c) is (r / 3) * 3 + (c / 3) using integer division.

3. Hint 3

   One pass over the 81 cells fills and checks all three families at once.

How to solve Valid Sudoku

Keep nine sets each for rows, columns and boxes; one pass over the 81 cells inserts each digit into its three sets and fails on any collision.

Approach

1. For each filled cell compute box = (r // 3) · 3 + c // 3.
2. Return false if the digit is already in rows[r], cols[c] or boxes[box].
3. Insert it into all three.

Why it works

Validity is exactly "no digit repeats within any row, column or box", and a set per group detects repeats as they appear.

Complexity

• Time — O(81)
• Space — O(81)

Pitfalls

• The box index formula is the one detail people get wrong — integer-divide both coordinates by 3.
• Bitmasks (nine ints per family) are the compact equivalent.

Reference solution

Python

def isValidSudoku(board) -> bool:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == 0:
                continue
            b = (r // 3) * 3 + c // 3
            if v in rows[r] or v in cols[c] or v in boxes[b]:
                return False
            rows[r].add(v)
            cols[c].add(v)
            boxes[b].add(v)
    return True

Java

public static boolean isValidSudoku(int[][] board) {
    boolean[][] rows = new boolean[9][10];
    boolean[][] cols = new boolean[9][10];
    boolean[][] boxes = new boolean[9][10];
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            int v = board[r][c];
            if (v == 0) continue;
            int box = (r / 3) * 3 + c / 3;
            if (rows[r][v] || cols[c][v] || boxes[box][v]) return false;
            rows[r][v] = true;
            cols[c][v] = true;
            boxes[box][v] = true;
        }
    }
    return true;
}

C++

bool isValidSudoku(vector<vector<int>>& board) {
    bool rows[9][10] = {{false}};
    bool cols[9][10] = {{false}};
    bool boxes[9][10] = {{false}};
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            int v = board[r][c];
            if (v == 0) continue;
            int box = (r / 3) * 3 + c / 3;
            if (rows[r][v] || cols[c][v] || boxes[box][v]) return false;
            rows[r][v] = true;
            cols[c][v] = true;
            boxes[box][v] = true;
        }
    }
    return true;
}

JavaScript

var isValidSudoku = function(board) {
    const rows = [], cols = [], boxes = [];
    for (let i = 0; i < 9; i++) {
        rows.push(new Set());
        cols.push(new Set());
        boxes.push(new Set());
    }
    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            const v = board[r][c];
            if (v === 0) continue;
            const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
            if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) return false;
            rows[r].add(v);
            cols[c].add(v);
            boxes[b].add(v);
        }
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium