36. Valid Sudoku Solution & Explanation

Q: Is Valid Sudoku easy or hard?

Valid Sudoku is generally categorized as a medium difficulty problem. The logic is straightforward once you separate row, column, and subgrid validation, but implementing the checks cleanly requires careful indexing and data structure selection.

Q: Valid Sudoku Python/Java solution

Python and Java solutions typically use three arrays of sets: one for rows, one for columns, and one for 3x3 boxes. During iteration, each digit is validated against these structures before insertion. The algorithm runs in O(n^2) time and is easy to implement in most languages.

Q: How to solve Valid Sudoku in O(n)?

The board must be checked cell by cell, so the practical complexity is O(n^2) for an n×n grid. However, each validation operation is constant time using hash sets or bit masks. This keeps the solution efficient even during full board traversal.

Q: What is the best approach for Valid Sudoku?

The hash set validation approach is the most common solution. Track digits seen in each row, column, and 3x3 subgrid using sets and detect duplicates in O(1) time. The full scan of the board takes O(n^2) time for a 9x9 grid. Bit manipulation is an optimized alternative with constant space.

Q: Is Valid Sudoku asked at Google/Amazon/Meta?

Valid Sudoku appears frequently in coding interviews and practice sets used by companies like Amazon, Google, and Meta. It tests array traversal, constraint validation, and efficient use of hash structures or bit manipulation.

Q: What data structure is used in Valid Sudoku?

The most common data structures are hash sets or hash maps to track digits seen in rows, columns, and boxes. An alternative implementation uses integer bitmasks to store digit presence more compactly while maintaining constant-time checks.

Q: What is the time complexity of Valid Sudoku?

Valid Sudoku runs in O(n^2) time because every cell in the board must be inspected once. For the standard 9x9 board this equals 81 checks, effectively constant time. Each validation step performs O(1) lookups using hash sets or bit masks.

The problem

Determine if a 9 x 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 x 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 according to the mentioned rules.

Example 1:

Input: 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"]]
Output: true

Example 2:

Input: board = 
[["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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

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

Approach overview

Problem Overview: You are given a partially filled 9x9 Sudoku board. The task is to determine whether the board configuration is valid. A valid board means each row, each column, and each 3x3 subgrid contains digits 1–9 without duplicates. Empty cells are represented by . and should be ignored during validation.

Approach 1: Hash Set Validation (Time: O(n^2), Space: O(n^2))

This approach tracks numbers seen in each row, column, and 3x3 box using hash sets. Iterate through the board cell by cell. When you encounter a digit, check whether it already exists in the corresponding row set, column set, or box set. If it does, the board is invalid. Otherwise insert the value into all three sets and continue scanning.

The key insight is treating rows, columns, and subgrids as independent constraints. A simple hash lookup (O(1)) detects duplicates immediately. You can compute the box index using (row / 3) * 3 + col / 3. This approach is straightforward and widely used in interview solutions involving hash tables and grid traversal problems built on arrays and matrix structures.

Approach 2: Bit Manipulation (Time: O(n^2), Space: O(1))

Bit manipulation compresses the same validation logic into integer bitmasks. Instead of hash sets, maintain three arrays: rows[9], cols[9], and boxes[9]. Each integer acts as a 9-bit mask representing digits 1–9. When processing a digit d, compute mask = 1 << (d - 1). If the mask already exists in the corresponding row, column, or box using a bitwise AND check, a duplicate was found.

If the digit is new, update the masks using bitwise OR. This technique eliminates dynamic data structures and reduces memory overhead while keeping constant-time checks. Bitmasking is common in constraint validation problems where the value range is small and fixed.

Recommended for interviews: The hash set solution is the most common answer and clearly communicates the validation logic. Interviewers expect you to recognize that rows, columns, and boxes must be tracked separately. The bit manipulation version demonstrates stronger optimization skills and understanding of low-level operations. Both run in O(n^2) time for a 9×9 board, but the bitmask approach achieves O(1) auxiliary space.

Approach 1: Approach 1: Hash Set Validation

This approach uses hash sets to track the unique numbers found in each row, column, and 3x3 sub-box. We iterate over each cell in the board, and check if the current value has been seen before in the current row, column, or sub-box. If it has, we return false. Otherwise, we add the value to the respective sets.

Python

def isValidSudoku(board):
    from collections import defaultdict
    rows = defaultdict(set)
    columns = defaultdict(set)
    boxes = defaultdict(set)
    for r in range(9):
        for c in range(9):
            if board[r][c] == '.':
                continue
            if (board[r][c] in rows[r] or 
                board[r][c] in columns[c] or 
                board[r][c] in boxes[(r // 3, c // 3)]):
                return False
            rows[r].add(board[r][c])
            columns[c].add(board[r][c])
            boxes[(r // 3, c // 3)].add(board[r][c])
    return True

Java

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

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    continue;
                }
                int num = board[r][c] - '1';
                int boxIndex = (r / 3) * 3 + c / 3;

                if (rows[r][num] || cols[c][num] || boxes[boxIndex][num]) {
                    return false;
                }
                rows[r][num] = true;
                cols[c][num] = true;
                boxes[boxIndex][num] = true;
            }
        }
        return true;
    }
}

C++

#include <vector>
using namespace std;

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool rows[9][9] = {false};
        bool cols[9][9] = {false};
        bool boxes[9][9] = {false};
        
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') continue;
                int num = board[r][c] - '1';
                int boxIndex = (r / 3) * 3 + c / 3;
                
                if (rows[r][num] || cols[c][num] || boxes[boxIndex][num]) {
                    return false;
                }
                rows[r][num] = true;
                cols[c][num] = true;
                boxes[boxIndex][num] = true;
            }
        }
        return true;
    }
};

JavaScript

function isValidSudoku(board) {
    const rows = new Array(9).fill(0).map(() => new Set());
    const cols = new Array(9).fill(0).map(() => new Set());
    const boxes = new Array(9).fill(0).map(() => new Set());

    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            if (board[r][c] === '.') continue;
            const num = board[r][c];
            const boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3);

            if (rows[r].has(num) || cols[c].has(num) || boxes[boxIndex].has(num)) {
                return false;
            }
            rows[r].add(num);
            cols[c].add(num);
            boxes[boxIndex].add(num);
        }
    }
    return true;
}

#include <stdbool.h>
#include <string.h>

bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
    bool row[9][9] = {false};
    bool col[9][9] = {false};
    bool box[9][9] = {false};
    
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.') {
                continue;
            }
            int num = board[r][c] - '1';
            int k = (r / 3) * 3 + c / 3;
            
            if (row[r][num] || col[c][num] || box[k][num]) {
                return false;
            }
            row[r][num] = true;
            col[c][num] = true;
            box[k][num] = true;
        }
    }
    return true;
}

public class Solution {
    public bool IsValidSudoku(char[][] board) {
        bool[,] rows = new bool[9, 9];
        bool[,] cols = new bool[9, 9];
        bool[,] boxes = new bool[9, 9];

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.')
                    continue;
                int num = board[r][c] - '1';
                int boxIndex = (r / 3) * 3 + c / 3;

                if (rows[r, num] || cols[c, num] || boxes[boxIndex, num]) {
                    return false;
                }
                rows[r, num] = true;
                cols[c, num] = true;
                boxes[boxIndex, num] = true;
            }
        }
        return true;
    }
}

This solution uses three dictionaries, each containing sets, to keep track of seen values in rows, columns, and boxes. The key for the boxes dictionary is a tuple representing the box index. As we iterate, we skip any empty cells and check if the number already exists in any of its corresponding set. If it does, the Sudoku is invalid. Otherwise, we add the number to the corresponding sets and continue.

Complexity

Time Complexity: O(1) because the board size is constant (9x9).
Space Complexity: O(1) due to the fixed size of additional data structures used.

Try this approach in the editor

Approach 2: Approach 2: Bit Manipulation

This approach seeks to replace sets with bit manipulations to compress space usage for tracking seen numbers. We increment bits in an integer representing whether a digit has been seen in rows, columns, or boxes.

Python

def isValidSudoku(board):
    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
    for r in range(9):
        for c in range(9):
            if board[r][c] == '.':
                continue
            val = 1 << (ord(board[r][c]) - ord('1'))
            box_index = (r // 3) * 3 + c // 3
            if (rows[r] & val) or (cols[c] & val) or (boxes[box_index] & val):
                return False
            rows[r] |= val
            cols[c] |= val
            boxes[box_index] |= val
    return True

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++) {
                if (board[r][c] == '.')
                    continue;
                int val = 1 << (board[r][c] - '1');
                int boxIndex = (r / 3) * 3 + c / 3;
                if ((rows[r] & val) > 0 || (cols[c] & val) > 0 || (boxes[boxIndex] & val) > 0) {
                    return false;
                }
                rows[r] |= val;
                cols[c] |= val;
                boxes[boxIndex] |= val;
            }
        }
        return true;
    }
}

C++

#include <vector>
using namespace std;

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int rows[9] = {0}, cols[9] = {0}, boxes[9] = {0};
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') continue;
                int bit = 1 << (board[r][c] - '1');
                int boxIndex = (r / 3) * 3 + c / 3;
                
                if ((rows[r] & bit) || (cols[c] & bit) || (boxes[boxIndex] & bit))
                    return false;
                rows[r] |= bit;
                cols[c] |= bit;
                boxes[boxIndex] |= bit;
            }
        }
        return true;
    }
};

JavaScript

function isValidSudoku(board) {
    let rows = Array(9).fill(0);
    let cols = Array(9).fill(0);
    let boxes = Array(9).fill(0);

    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            if (board[r][c] === '.') continue;
            const bit = 1 << (board[r][c] - '1');
            const boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3);

            if ((rows[r] & bit) || (cols[c] & bit) || (boxes[boxIndex] & bit)) {
                return false;
            }
            rows[r] |= bit;
            cols[c] |= bit;
            boxes[boxIndex] |= bit;
        }
    }
    return true;
}

#include <stdbool.h>

bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
    int row[9] = {0}, col[9] = {0}, box[9] = {0};
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.')
                continue;
            int num = board[r][c] - '1';
            int val = 1 << num;
            int boxIndex = (r / 3) * 3 + c / 3;
            if ((row[r] & val) || (col[c] & val) || (box[boxIndex] & val))
                return false;
            row[r] |= val;
            col[c] |= val;
            box[boxIndex] |= val;
        }
    }
    return true;
}

public class Solution {
    public bool 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++) {
                if (board[r][c] == '.')
                    continue;
                int val = 1 << (board[r][c] - '1');
                int boxIndex = (r / 3) * 3 + c / 3;

                if ((rows[r] & val) != 0 || (cols[c] & val) != 0 || (boxes[boxIndex] & val) != 0) {
                    return false;
                }
                rows[r] |= val;
                cols[c] |= val;
                boxes[boxIndex] |= val;
            }
        }
        return true;
    }
}

This solution uses integers to record seen numbers in binary form. Each place represents whether a number has been seen (responding to the power of 2 in terms of bit location).

Complexity

Time Complexity: O(1) as the board size and iteration steps remain constant.
Space Complexity: O(1) due to the integer used for tracking positions, which is constant.

Try this approach in the editor

Approach 3: Traversal once

The valid sudoku satisfies the following three conditions:

The digits are not repeated in each row;
The digits are not repeated in each column;
The digits are not repeated in each 3 times 3 box.

Traverse the sudoku, for each digit, check whether the row, column and 3 times 3 box it is in have appeared the digit. If it is, return false. If the traversal is over, return true.

The time complexity is O(C) and the space complexity is O(C), where C is the number of empty spaces in the sudoku. In this question, C=81.

TypeScript

function isValidSudoku(board: string[][]): boolean {
    const row: boolean[][] = Array.from({ length: 9 }, () =>
        Array.from({ length: 9 }, () => false),
    );
    const col: boolean[][] = Array.from({ length: 9 }, () =>
        Array.from({ length: 9 }, () => false),
    );
    const sub: boolean[][] = Array.from({ length: 9 }, () =>
        Array.from({ length: 9 }, () => false),
    );
    for (let i = 0; i < 9; ++i) {
        for (let j = 0; j < 9; ++j) {
            const num = board[i][j].charCodeAt(0) - '1'.charCodeAt(0);
            if (num < 0 || num > 8) {
                continue;
            }
            const k = Math.floor(i / 3) * 3 + Math.floor(j / 3);
            if (row[i][num] || col[j][num] || sub[k][num]) {
                return false;
            }
            row[i][num] = true;
            col[j][num] = true;
            sub[k][num] = true;
        }
    }
    return true;
}

func isValidSudoku(board [][]byte) bool {
	row, col, sub := [9][9]bool{}, [9][9]bool{}, [9][9]bool{}
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			num := board[i][j] - byte('1')
			if num < 0 || num > 9 {
				continue
			}
			k := i/3*3 + j/3
			if row[i][num] || col[j][num] || sub[k][num] {
				return false
			}
			row[i][num] = true
			col[j][num] = true
			sub[k][num] = true
		}
	}
	return true
}

Rust

impl Solution {
    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        let mut row = vec![vec![false; 9]; 9];
        let mut col = vec![vec![false; 9]; 9];
        let mut sub = vec![vec![false; 9]; 9];

        for i in 0..9 {
            for j in 0..9 {
                let c = board[i][j];
                if c == '.' {
                    continue;
                }
                let num = (c as u8 - b'0' - 1) as usize;
                let k = i / 3 * 3 + j / 3;
                if row[i][num] || col[j][num] || sub[k][num] {
                    return false;
                }
                row[i][num] = true;
                col[j][num] = true;
                sub[k][num] = true;
            }
        }
        true
    }
}

PHP

class Solution {
    /**
     * @param String[][] $board
     * @return Boolean
     */
    function isValidSudoku($board) {
        $row = array_fill(0, 9, array_fill(0, 9, false));
        $col = array_fill(0, 9, array_fill(0, 9, false));
        $sub = array_fill(0, 9, array_fill(0, 9, false));

        for ($i = 0; $i < 9; $i++) {
            for ($j = 0; $j < 9; $j++) {
                $c = $board[$i][$j];
                if ($c === '.') {
                    continue;
                }
                $num = intval($c) - 1;
                $k = intdiv($i, 3) * 3 + intdiv($j, 3);
                if ($row[$i][$num] || $col[$j][$num] || $sub[$k][$num]) {
                    return false;
                }
                $row[$i][$num] = true;
                $col[$j][$num] = true;
                $sub[$k][$num] = true;
            }
        }
        return true;
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Hash Set Validation	Time Complexity: O(1) because the board size is constant (9x9). Space Complexity: O(1) due to the fixed size of additional data structures used.
Approach 2: Bit Manipulation	Time Complexity: O(1) as the board size and iteration steps remain constant. Space Complexity: O(1) due to the integer used for tracking positions, which is constant.
Traversal once	–

Complexity analysis

Approach	Time	Space	When to Use
Hash Set Validation	O(n^2)	O(n^2)	Best for readability and interviews; straightforward duplicate detection using hash lookups
Bit Manipulation	O(n^2)	O(1)	Memory‑efficient solution when the value range is fixed (digits 1–9)

Frequently asked questions

Is Valid Sudoku easy or hard?

Valid Sudoku is generally categorized as a medium difficulty problem. The logic is straightforward once you separate row, column, and subgrid validation, but implementing the checks cleanly requires careful indexing and data structure selection.

Valid Sudoku Python/Java solution

Python and Java solutions typically use three arrays of sets: one for rows, one for columns, and one for 3x3 boxes. During iteration, each digit is validated against these structures before insertion. The algorithm runs in O(n^2) time and is easy to implement in most languages.

How to solve Valid Sudoku in O(n)?

The board must be checked cell by cell, so the practical complexity is O(n^2) for an n×n grid. However, each validation operation is constant time using hash sets or bit masks. This keeps the solution efficient even during full board traversal.

What is the best approach for Valid Sudoku?

The hash set validation approach is the most common solution. Track digits seen in each row, column, and 3x3 subgrid using sets and detect duplicates in O(1) time. The full scan of the board takes O(n^2) time for a 9x9 grid. Bit manipulation is an optimized alternative with constant space.

Is Valid Sudoku asked at Google/Amazon/Meta?

Valid Sudoku appears frequently in coding interviews and practice sets used by companies like Amazon, Google, and Meta. It tests array traversal, constraint validation, and efficient use of hash structures or bit manipulation.

What data structure is used in Valid Sudoku?

The most common data structures are hash sets or hash maps to track digits seen in rows, columns, and boxes. An alternative implementation uses integer bitmasks to store digit presence more compactly while maintaining constant-time checks.

What is the time complexity of Valid Sudoku?

Valid Sudoku runs in O(n^2) time because every cell in the board must be inspected once. For the standard 9x9 board this equals 81 checks, effectively constant time. Each validation step performs O(1) lookups using hash sets or bit masks.

Valid Sudoku solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Hash Set Validation

Approach 2: Approach 2: Bit Manipulation

Approach 3: Traversal once

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Valid Sudoku solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Hash Set Validation

Approach 2: Approach 2: Bit Manipulation

Approach 3: Traversal once

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems