Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
1-9 without repetition.1-9 without repetition.3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.Note:
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 == 9board[i].length == 9board[i][j] is a digit 1-9 or '.'.To solve Valid Sudoku, the goal is to verify that a partially filled 9 x 9 Sudoku board follows the rules: each digit from 1–9 must appear at most once in every row, column, and each 3 x 3 sub-box. The common approach is to iterate through the board while tracking seen numbers using hash sets or similar structures.
For every cell that contains a digit (ignore '.'), check whether the number has already appeared in the current row, column, or its corresponding 3 x 3 box. These can be tracked using three collections: one for rows, one for columns, and one for boxes. If a duplicate is found in any of them, the board is invalid.
This method ensures constant-time lookups using hashing while scanning the matrix only once. Since the Sudoku board size is fixed (9 x 9), the runtime is effectively constant, though conceptually it is proportional to the number of cells.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set tracking for rows, columns, and 3x3 boxes | O(n²) (81 cells for standard board) | O(n²) for tracking sets |
| Bitmask / Boolean array optimization | O(n²) | O(1) |
NeetCode
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.
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.
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 bool isValidSudoku(vector<vector<char>>& board) {
7 bool rows[9][9] = {false};
8 bool cols[9][9] = {false};
9 bool boxes[9][9] = {false};
10
11 for (int r = 0; r < 9; r++) {
12 for (int c = 0; c < 9; c++) {
13 if (board[r][c] == '.') continue;
14 int num = board[r][c] - '1';
15 int boxIndex = (r / 3) * 3 + c / 3;
16
17 if (rows[r][num] || cols[c][num] || boxes[boxIndex][num]) {
18 return false;
19 }
20 rows[r][num] = true;
21 cols[c][num] = true;
22 boxes[boxIndex][num] = true;
23 }
24 }
25 return true;
26 }
27};This C++ solution is akin to the C and Java solutions, using arrays to keep track of seen digits and validating each digit as we traverse the board.
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.
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.
1defWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The optimal approach scans the board once while using hash sets or boolean arrays to track digits seen in each row, column, and 3x3 sub-box. If a digit appears twice in any of these groups, the board is invalid. This allows constant-time lookups and efficient validation.
Hash sets or fixed-size boolean arrays are commonly used because they provide fast O(1) checks for duplicates. They help track digits for rows, columns, and sub-boxes efficiently while iterating through the grid.
Yes, Valid Sudoku is a common matrix and hashing interview question. It tests a candidate's ability to manage constraints, use hash-based structures, and handle 2D array traversal effectively.
A standard Sudoku board always contains 81 cells, so the algorithm processes a fixed number of elements. Even though the theoretical complexity is O(n²), in practice it behaves like constant time because the board size never changes.
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).