Valid Sudoku

Problem Statement

Determine if a 9 × 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

• Each row must contain the digits 1–9 without repetition.
• Each column must contain the digits 1–9 without repetition.
• Each of the nine 3×3 sub-boxes of the grid must contain the digits 1–9 without repetition.

Note: A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated.

What to notice first

• The hardest part is the box index formula: box = (row // 3) * 3 + (col // 3)
• '.' represents an empty cell — skip those entirely.
• This is a validation problem, not a solving problem — you only check that no digit appears twice, not that a solution exists.

Examples

Board	Valid?	Reason
Standard partially filled valid board	✓	No duplicates in any row, column, or box
Board with '8' repeated in the same row	✗	Duplicate 8 in row 0

Valid board (first 3 rows shown):

["5","3",".",".","7",".",".",".","."]
["6",".",".","1","9","5",".",".","."]
[".","9","8",".",".",".",".","6","."]

No digit repeats in any row, column, or 3×3 box — valid.

Invalid board:

["8","8",".",".","7",".",".",".","."]
...

'8' appears twice in row 0 — invalid.

Constraints

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit '1'–'9' or '.'

Real-World Applications

Where this pattern appears

• Constraint satisfaction validation — checking that a partially completed puzzle satisfies all constraints before solving.
• Spreadsheet validation — detecting conflicts in constraint-based cell value assignments.
• Exam seating arrangements — verifying no two students with the same topic are in the same row, column, or block.
• Resource allocation — ensuring no two processes require the same resource in overlapping time slots.

Complexity Comparison

Approach	Time	Space	Best When
Hash Sets	O(1)	O(1)	Board is always 9×9 — both are constant
Bitmask	O(1)	O(1)	Micro-optimisation, avoids hash overhead

Both are O(1) since the board size is fixed at 9×9.

Which approach should you learn first?

• Pick Hash Sets for interviews — it reads naturally and is easy to explain.
• Pick Bitmask as a follow-up to show you can eliminate hash overhead with integer operations.

Most Readable

Hash Sets

O(1) time · O(1) space

Fastest in Practice

Bitmask

O(1) time · O(1) space

Approach 1: Hash Sets

★ Recommended

Use three arrays of 9 sets — rows[9], cols[9], boxes[9] — to track which digits have been seen. For every non-empty cell (r, c) with digit d:

1. Compute box = (r // 3) * 3 + (c // 3)
2. If d is already in rows[r], cols[c], or boxes[box] → return false
3. Otherwise add d to all three sets

If no conflict is found after all 81 cells → return true.

⏱ Time O(1) 81 cells fixed 💾 Space O(1) 27 sets of ≤9 digits

Box Index Derivation

The 9 boxes are numbered 0–8 left-to-right, top-to-bottom:

rows \ cols	0–2	3–5	6–8
0–2	box 0	box 1	box 2
3–5	box 3	box 4	box 5
6–8	box 6	box 7	box 8

Formula: box = (row // 3) * 3 + (col // 3)

Step-by-step: Processing row 0

Sample row 0: ["5","3",".",".","7",".",".",".","."]

Step	(r, c)	d	box	rows[0] after	cols[c] after	boxes[box] after
1	(0, 0)	5	0	{5}	{5}	{5}
2	(0, 1)	3	0	{5,3}	{3}	{5,3}
3	(0, 2)	.	—	skip	skip	skip
4	(0, 3)	.	—	skip	skip	skip
5	(0, 4)	7	1	{5,3,7}	{7}	{7}
…	…	.	—	skip	skip	skip

Animated walkthrough

Hash sets tracking row 0 of a valid Sudoku board

Use Next or Autoplay to see each cell visited and its digit added to the row, column, and box sets.

Back Autoplay Next Reset

Step 1 of 6

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function isValidSudoku(board):
    rows  = 9 empty sets
    cols  = 9 empty sets
    boxes = 9 empty sets
    for r in 0..8:
        for c in 0..8:
            d = board[r][c]
            if d == '.': continue
            box = (r // 3) * 3 + (c // 3)
            if d in rows[r] or d in cols[c] or d in boxes[box]:
                return false
            add d to rows[r], cols[c], boxes[box]
    return true

Solution Code

Python

valid_sudoku_hash_sets.py

from typing import List
from collections import defaultdict


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

    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == '.':
                continue
            box = (r // 3) * 3 + (c // 3)
            if d in rows[r] or d in cols[c] or d in boxes[box]:
                return False
            rows[r].add(d)
            cols[c].add(d)
            boxes[box].add(d)

    return True

C++

valid_sudoku_hash_sets.cpp

#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<char> rows[9], cols[9], boxes[9];

        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                char d = board[r][c];
                if (d == '.') continue;
                int box = (r / 3) * 3 + (c / 3);
                if (rows[r].count(d) || cols[c].count(d) || boxes[box].count(d))
                    return false;
                rows[r].insert(d);
                cols[c].insert(d);
                boxes[box].insert(d);
            }
        }
        return true;
    }
};

Java

valid_sudoku_hash_sets.java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<Character>[] rows  = new HashSet[9];
        Set<Character>[] cols  = new HashSet[9];
        Set<Character>[] boxes = new HashSet[9];

        for (int i = 0; i < 9; i++) {
            rows[i]  = new HashSet<>();
            cols[i]  = new HashSet<>();
            boxes[i] = new HashSet<>();
        }

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char d = board[r][c];
                if (d == '.') continue;
                int box = (r / 3) * 3 + (c / 3);
                if (rows[r].contains(d) || cols[c].contains(d) || boxes[box].contains(d))
                    return false;
                rows[r].add(d);
                cols[c].add(d);
                boxes[box].add(d);
            }
        }
        return true;
    }
}

JavaScript

valid_sudoku_hash_sets.js

function isValidSudoku(board) {
    const rows  = Array.from({ length: 9 }, () => new Set());
    const cols  = Array.from({ length: 9 }, () => new Set());
    const boxes = Array.from({ length: 9 }, () => new Set());

    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            const d = board[r][c];
            if (d === '.') continue;
            const box = Math.floor(r / 3) * 3 + Math.floor(c / 3);
            if (rows[r].has(d) || cols[c].has(d) || boxes[box].has(d)) return false;
            rows[r].add(d);
            cols[c].add(d);
            boxes[box].add(d);
        }
    }
    return true;
}

Rust

valid_sudoku_hash_sets.rs

use std::collections::HashSet;

impl Solution {
    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        let mut rows:  [HashSet<char>; 9] = Default::default();
        let mut cols:  [HashSet<char>; 9] = Default::default();
        let mut boxes: [HashSet<char>; 9] = Default::default();

        for r in 0..9 {
            for c in 0..9 {
                let d = board[r][c];
                if d == '.' { continue; }
                let b = (r / 3) * 3 + (c / 3);
                if !rows[r].insert(d) || !cols[c].insert(d) || !boxes[b].insert(d) {
                    return false;
                }
            }
        }
        true
    }
}

Go

valid_sudoku_hash_sets.go

func isValidSudoku(board [][]byte) bool {
    var rows, cols, boxes [9]map[byte]bool
    for i := 0; i < 9; i++ {
        rows[i]  = map[byte]bool{}
        cols[i]  = map[byte]bool{}
        boxes[i] = map[byte]bool{}
    }

    for r := 0; r < 9; r++ {
        for c := 0; c < 9; c++ {
            d := board[r][c]
            if d == '.' {
                continue
            }
            b := (r/3)*3 + (c / 3)
            if rows[r][d] || cols[c][d] || boxes[b][d] {
                return false
            }
            rows[r][d] = true
            cols[c][d] = true
            boxes[b][d] = true
        }
    }
    return true
}

Approach 2: Bitmask

🎯 Interview Favourite

Replace each set with a single integer. Bit k (0-indexed) is set when digit k+1 has been seen. This eliminates hash overhead and reduces each check to a bitwise AND.

• Check digit d: (mask >> (d - 1)) & 1 == 1
• Set digit d: mask |= (1 << (d - 1))

⏱ Time O(1) 81 cells fixed 💾 Space O(1) 27 integers

Bitmask Example

For digit 5: bit index = 5 - 1 = 4, so bit pattern = 0b000010000 (bit 4 set).

Digit seen	Bit set	mask value
5	bit 4	0b000010000 = 16
3	bit 2	0b000010100 = 20
7	bit 6	0b001010100 = 84

To check if 3 is already in this mask: 84 & (1 << 2) = 84 & 4 = 4 ≠ 0 → duplicate detected.

Pseudocode

function isValidSudoku(board):
    rows  = [0] * 9
    cols  = [0] * 9
    boxes = [0] * 9
    for r in 0..8:
        for c in 0..8:
            d = board[r][c]
            if d == '.': continue
            bit = 1 << (int(d) - 1)
            box = (r // 3) * 3 + (c // 3)
            if rows[r] & bit or cols[c] & bit or boxes[box] & bit:
                return false
            rows[r]  |= bit
            cols[c]  |= bit
            boxes[box] |= bit
    return true

Solution Code

Python

valid_sudoku_bitmask.py

from typing import List


def isValidSudoku(board: List[List[str]]) -> bool:
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9

    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == '.':
                continue
            bit = 1 << (int(d) - 1)
            box = (r // 3) * 3 + (c // 3)
            if rows[r] & bit or cols[c] & bit or boxes[box] & bit:
                return False
            rows[r] |= bit
            cols[c] |= bit
            boxes[box] |= bit

    return True

C++

valid_sudoku_bitmask.cpp

#include <vector>
using namespace std;

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int rows[9] = {}, cols[9] = {}, boxes[9] = {};

        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                char d = board[r][c];
                if (d == '.') continue;
                int bit = 1 << (d - '1');
                int box = (r / 3) * 3 + (c / 3);
                if ((rows[r] & bit) || (cols[c] & bit) || (boxes[box] & bit))
                    return false;
                rows[r] |= bit;
                cols[c] |= bit;
                boxes[box] |= bit;
            }
        }
        return true;
    }
};

Java

valid_sudoku_bitmask.java

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] rows  = new int[9];
        int[] cols  = new int[9];
        int[] boxes = new int[9];

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char d = board[r][c];
                if (d == '.') continue;
                int bit = 1 << (d - '1');
                int box = (r / 3) * 3 + (c / 3);
                if ((rows[r] & bit) != 0 || (cols[c] & bit) != 0 || (boxes[box] & bit) != 0)
                    return false;
                rows[r]  |= bit;
                cols[c]  |= bit;
                boxes[box] |= bit;
            }
        }
        return true;
    }
}

JavaScript

valid_sudoku_bitmask.js

function isValidSudoku(board) {
    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 d = board[r][c];
            if (d === '.') continue;
            const bit = 1 << (parseInt(d) - 1);
            const box = Math.floor(r / 3) * 3 + Math.floor(c / 3);
            if ((rows[r] & bit) || (cols[c] & bit) || (boxes[box] & bit)) return false;
            rows[r]  |= bit;
            cols[c]  |= bit;
            boxes[box] |= bit;
        }
    }
    return true;
}

Rust

valid_sudoku_bitmask.rs

impl Solution {
    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        let mut rows  = [0u16; 9];
        let mut cols  = [0u16; 9];
        let mut boxes = [0u16; 9];

        for r in 0..9 {
            for c in 0..9 {
                let d = board[r][c];
                if d == '.' { continue; }
                let bit: u16 = 1 << (d as u16 - '1' as u16);
                let b = (r / 3) * 3 + (c / 3);
                if (rows[r] & bit) != 0 || (cols[c] & bit) != 0 || (boxes[b] & bit) != 0 {
                    return false;
                }
                rows[r]  |= bit;
                cols[c]  |= bit;
                boxes[b] |= bit;
            }
        }
        true
    }
}

Go

valid_sudoku_bitmask.go

func isValidSudoku(board [][]byte) bool {
    var rows, cols, boxes [9]int

    for r := 0; r < 9; r++ {
        for c := 0; c < 9; c++ {
            d := board[r][c]
            if d == '.' {
                continue
            }
            bit := 1 << (d - '1')
            b := (r/3)*3 + (c / 3)
            if rows[r]&bit != 0 || cols[c]&bit != 0 || boxes[b]&bit != 0 {
                return false
            }
            rows[r] |= bit
            cols[c] |= bit
            boxes[b] |= bit
        }
    }
    return true
}

Common mistakes

• Incorrect box index formula — the correct formula is (row // 3) * 3 + (col // 3), not row * 3 + col or any other variant.
• Forgetting to skip '.' cells — attempting to insert or check '.' corrupts all three sets/masks.
• Thinking completeness is required — you only need to confirm no digit appears twice among the filled cells; an incomplete board can still be valid.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

valid_sudoku_space_optimized.py

"""
Solution for Valid Sudoku
"""

def solve():
    """Implementation for approach 3 of Valid Sudoku"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

valid_sudoku_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Valid Sudoku
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ValidSudokuSpaceOptimized.java

/**
 * Solution for Valid Sudoku
 * Approach 3
 */
public class ValidSudokuSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

valid_sudoku_space_optimized.js

/**
 * Solution for Valid Sudoku
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

valid_sudoku_space_optimized.rs

/// Solution for Valid Sudoku
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

valid_sudoku_space_optimized.go

package main

import "fmt"

// Solution for Valid Sudoku
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Sudoku Solver ↗ Hard #37
• Group Anagrams ↗ Medium #49
• Set Matrix Zeroes ↗ Medium #73

Interview Tips

Key points to communicate

• State the box formula immediately — (row // 3) * 3 + (col // 3) is the one part that trips people up, so say it out loud early.
• Both approaches are O(1) time and space because the board is fixed-size (9×9) — the constant 81 cells and 27 tracking structures never grow.
• The bitmask approach is a clean follow-up — “I can do this with 27 integers instead of 27 sets, replacing hash operations with bitwise AND/OR.”
• Practice tracing the box index — verify: (0,0)→0, (0,3)→1, (3,0)→3, (4,4)→4, (8,8)→8.

← Previous
#35 Search Insert Position Next
#39 Combination Sum →