Log inSign up
mediumLeetCodeNot Started

Valid Sudoku

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following 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 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
Explanation: Each row, column, and 3x3 sub-box contains unique digits from 1-9.

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 top-left cell changed to 8. Since there are two 8s in the first column and 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 ..

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D Array / Matrix Indexing
  • Hash Set / Boolean Frequency Array
  • Bitwise Shift & Mask Operations

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master 2D to 1D mapping for grid subdivisions: (r / 3) * 3 + (c / 3).
  • Understand multi-projection validation (row, column, and subgrid) in a single unified loop.
  • Implement bitmask-based frequency sets for memory-efficient fixed-range tracking (digits 1-9).
  • Distinguish between validating board states vs solving boards (Backtracking vs Validation).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • 2D grid constraint validation on rows, columns, and subgrids.
  • Checking uniqueness across multiple intersecting coordinate projections.
  • Fixed input dimensions (9x9).

Algorithmic Decision Tree:

  • Box index formula: boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3).
  • For digit val = board[r][c] - '1' (0-indexed):
  • Check rows[r][val], cols[c][val], boxes[boxIndex][val]. If true, return false.
  • Otherwise, mark all three as true.

Connected Patterns:

Sudoku Solver (Backtracking with the same validity checker)Valid Tic-Tac-Toe State (Constraint checking across rows/cols/diagonals)Game of Life (Matrix neighbor indexing)

1. Triple Pass Check (Row, Col, Box Separately)

Intuition

Validate each constraint separately: first verify all 9 rows for duplicates, then all 9 columns, then all 9 3x3 boxes.

Algorithm

  1. Check rows: For each row r, use a boolean array to check digits 1-9.
  2. Check cols: For each col c, use a boolean array to check digits 1-9.
  3. Check boxes: For each 3x3 subgrid starting at (br, bc), check digits 1-9.
  4. If any duplicate is detected, return false.
  5. If all pass, return true.

Triple Pass Check Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [Pass 1: Rows (9), Pass 2: Cols (9), Pass 3: Boxes (9), 81 cells total]
Current operationSTEP 1 OF 6
Pass 1 (Rows): Iterate rows 0 to 8
Visual state
Values and pointers at this exact step
pointers
S
ROWS
0
↑ Row check
Variables at this step
pass
1
target
rows
row0Valid
true
Check / comparison
Validate row 0: '5', '3', '7'
Decision / next transition
All digits in row 0 are distinct. Continue across all 9 rows.
Why this step matters

Pass 1 (Rows): Iterate rows 0 to 8. For each row, use a HashSet seen.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4
5class Solution {
6public:
7 bool isValidSudoku(std::vector<std::vector<char>>& board) {
8 // 1. Check rows
9 for (int r = 0; r < 9; ++r) {
10 std::vector<bool> seen(10, false);
11 for (int c = 0; c < 9; ++c) {
12 if (board[r][c] != '.') {
13 int val = board[r][c] - '0';
14 if (seen[val]) return false;
15 seen[val] = true;
16 }
17 }
18 }
19
20 // 2. Check cols
21 for (int c = 0; c < 9; ++c) {
22 std::vector<bool> seen(10, false);
23 for (int r = 0; r < 9; ++r) {
24 if (board[r][c] != '.') {
25 int val = board[r][c] - '0';
26 if (seen[val]) return false;
27 seen[val] = true;
28 }
29 }
30 }
31
32 // 3. Check 3x3 boxes
33 for (int box = 0; box < 9; ++box) {
34 std::vector<bool> seen(10, false);
35 int startR = (box / 3) * 3;
36 int startC = (box % 3) * 3;
37 for (int r = 0; r < 3; ++r) {
38 for (int c = 0; c < 3; ++c) {
39 char cell = board[startR + r][startC + c];
40 if (cell != '.') {
41 int val = cell - '0';
42 if (seen[val]) return false;
43 seen[val] = true;
44 }
45 }
46 }
47 }
48
49 return true;
50 }
51};
52
53int main() {
54 Solution sol;
55 std::vector<std::vector<char>> board = {
56 {'5','3','.','.','7','.','.','.','.'},
57 {'6','.','.','1','9','5','.','.','.'},
58 {'.','9','8','.','.','.','.','6','.'},
59 {'8','.','.','.','6','.','.','.','3'},
60 {'4','.','.','8','.','3','.','.','1'},
61 {'7','.','.','.','2','.','.','.','6'},
62 {'.','6','.','.','.','.','2','8','.'},
63 {'.','.','.','4','1','9','.','.','5'},
64 {'.','.','.','.','8','.','.','7','9'}
65 };
66 std::cout << (sol.isValidSudoku(board) ? "true" : "false") << std::endl; // Output: true
67 return 0;
68}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Triple Pass Check (Row, Col, Box Separately).
  • Space complexity: O(1) — Space complexity for Triple Pass Check (Row, Col, Box Separately).

Why Brute Force Doesn't Scale:

While 81 iterations is small, heap allocations and hash function computations add unnecessary CPU cycle overhead.

Bitmasking with 9-bit integers executes in under 500 nanoseconds using standard CPU register bitwise instructions.

2. Single Pass with HashSet Encoding

Intuition

Traverse the board in a single pass. For each cell (r, c) with digit val, insert 3 encoded strings into a Set: "r{r}-{val}", "c{c}-{val}", "b{r/3}{c/3}-{val}". If any string already exists in the Set, return false.

Algorithm

  1. Initialize a hash set seen.
  2. Loop r from 0 to 8 and c from 0 to 8.
  3. If board[r][c] != '.':
  4. Let val = board[r][c].
  5. Create row key, col key, and box key.
  6. If any of these 3 keys already exist in seen, return false.
  7. Insert all 3 keys into seen.
  8. Return true.

Single Pass with HashSet Encoding Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = ['5 in row 0', '5 in col 0', '5 in box 0', '3 in row 0', '6 in col 0']
Current operationSTEP 1 OF 6
Initialize single HashSet seen
Visual state
Values and pointers at this exact step
pointers
S
'5 in row 0'
'5 in col 0'
'5 in box 0'
0
↑ cell (0,0)
1
2
Variables at this step
r
0
c
0
val
5
box
0
added
3
Check / comparison
seen.contains('5 in row 0') == false
Decision / next transition
Add keys '5 in row 0', '5 in col 0', '5 in box 0'. All absent, proceed.
Why this step matters

Initialize single HashSet seen. Cell (0,0) holds 5. Box b = (0/3)*3 + (0/3) = 0.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4#include <string>
5
6class Solution {
7public:
8 bool isValidSudoku(std::vector<std::vector<char>>& board) {
9 std::unordered_set<std::string> seen;
10 for (int r = 0; r < 9; ++r) {
11 for (int c = 0; c < 9; ++c) {
12 char ch = board[r][c];
13 if (ch != '.') {
14 std::string rowKey = "r" + std::to_string(r) + ch;
15 std::string colKey = "c" + std::to_string(c) + ch;
16 std::string boxKey = "b" + std::to_string(r / 3) + std::to_string(c / 3) + ch;
17
18 if (seen.count(rowKey) || seen.count(colKey) || seen.count(boxKey)) {
19 return false;
20 }
21 seen.insert(rowKey);
22 seen.insert(colKey);
23 seen.insert(boxKey);
24 }
25 }
26 }
27 return true;
28 }
29};
30
31int main() {
32 Solution sol;
33 std::vector<std::vector<char>> board = {
34 {'5','3','.','.','7','.','.','.','.'},
35 {'6','.','.','1','9','5','.','.','.'},
36 {'.','9','8','.','.','.','.','6','.'},
37 {'8','.','.','.','6','.','.','.','3'},
38 {'4','.','.','8','.','3','.','.','1'},
39 {'7','.','.','.','2','.','.','.','6'},
40 {'.','6','.','.','.','.','2','8','.'},
41 {'.','.','.','4','1','9','.','.','5'},
42 {'.','.','.','.','8','.','.','7','9'}
43 };
44 std::cout << (sol.isValidSudoku(board) ? "true" : "false") << std::endl; // Output: true
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Single Pass with HashSet Encoding.
  • Space complexity: O(N) — Space complexity for Single Pass with HashSet Encoding.

3. Single Pass with 2D Boolean Arrays / Bitmasking

Intuition

Maintain three 9x9 boolean tables (or integer bitmasks) for rows, columns, and 3x3 boxes. In a single scan of 81 cells, map boxIndex = (r / 3) * 3 + (c / 3) and check/set the corresponding flag in O(1) time without any dynamic allocations.

Algorithm

  1. Initialize rows[9][9] = false, cols[9][9] = false, boxes[9][9] = false.
  2. Iterate r from 0 to 8:
  3. Iterate c from 0 to 8:
  4. If board[r][c] == '.', continue.
  5. Let num = board[r][c] - '1' (0-indexed 0..8).
  6. Let boxIdx = (r / 3) * 3 + (c / 3).
  7. If rows[r][num] or cols[c][num] or boxes[boxIdx][num] is true, return false.
  8. Mark rows[r][num] = cols[c][num] = boxes[boxIdx][num] = true.
  9. Return true.

Single Pass with Bitmasking Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [rows[9]=0, cols[9]=0, boxes[9]=0, mask = 1 << (val - 1)]
Current operationSTEP 1 OF 6
Allocate 3 integer arrays: rows[9], cols[9], boxes[9] initialized to 0
Visual state
Values and pointers at this exact step
pointers
S
int[9]
int[9]
int[9]
0
↑ bitmasks
1
2
Variables at this step
rows
[0,0,0,0,0,0,0,0,0]
cols
[0,0,0,0,0,0,0,0,0]
boxes
[0,0,0,0,0,0,0,0,0]
Check / comparison
Bitmask setup
Decision / next transition
Each bit position k represents presence of digit k+1.
Why this step matters

Allocate 3 integer arrays: rows[9], cols[9], boxes[9] initialized to 0.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 bool isValidSudoku(std::vector<std::vector<char>>& board) {
7 // rows[r][d], cols[c][d], boxes[b][d] store presence of digit d (0-8)
8 bool rows[9][9] = {false};
9 bool cols[9][9] = {false};
10 bool boxes[9][9] = {false};
11
12 for (int r = 0; r < 9; ++r) {
13 for (int c = 0; c < 9; ++c) {
14 if (board[r][c] == '.') continue;
15
16 int num = board[r][c] - '1'; // Map __SF_TOKEN_B__-__SF_TOKEN_C__ to 0-8
17 int boxIdx = (r / 3) * 3 + (c / 3);
18
19 if (rows[r][num] || cols[c][num] || boxes[boxIdx][num]) {
20 return false; // Duplicate detected
21 }
22
23 rows[r][num] = true;
24 cols[c][num] = true;
25 boxes[boxIdx][num] = true;
26 }
27 }
28
29 return true;
30 }
31};
32
33int main() {
34 Solution sol;
35 std::vector<std::vector<char>> board = {
36 {'5','3','.','.','7','.','.','.','.'},
37 {'6','.','.','1','9','5','.','.','.'},
38 {'.','9','8','.','.','.','.','6','.'},
39 {'8','.','.','.','6','.','.','.','3'},
40 {'4','.','.','8','.','3','.','.','1'},
41 {'7','.','.','.','2','.','.','.','6'},
42 {'.','6','.','.','.','.','2','8','.'},
43 {'.','.','.','4','1','9','.','.','5'},
44 {'.','.','.','.','8','.','.','7','9'}
45 };
46 std::cout << (sol.isValidSudoku(board) ? "true" : "false") << std::endl; // Output: true
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Single Pass with 2D Boolean Arrays / Bitmasking.
  • Space complexity: O(1) — Space complexity for Single Pass with 2D Boolean Arrays / Bitmasking.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Triple Pass (Separate Row, Col, Box Scans)O(1) (81 cells x 3 passes = 243 operations)O(1)Pass 1: check rows. Pass 2: check cols. Pass 3: check 3x3 boxes.Multiple scans over memory.
2.Single Pass Hash Set with String KeysO(1) (81 cells single pass)O(1)Encode string representations like "4 in row 0", "4 in col 2", "4 in box 0-0". Add to a single Set.Dynamic memory allocations for string concatenation.
3.Single Pass Bitmasking / 2D Boolean ArraysOptimalO(1) (81 operations, single pass)O(1) (zero dynamic allocation, cache-friendly stack array)Track digit presence using bit shifts: rows[r] & (1 << digit).None. Directly accesses fixed 9-element arrays.

Common Pitfalls & Crucial Edge Cases

Incorrect 3x3 Box Formula

Writing (r % 3) * 3 + (c % 3) instead of Math.floor(r / 3) * 3 + Math.floor(c / 3).

Attempting Backtracking/Solving

Trying to solve the Sudoku puzzle instead of simply checking the currently filled cells for rule violations.

1-Based vs 0-Based Indexing for Bitmask

Shifting 1 << val where val = ch - '0' uses 10 bits; subtracting '1' maps cleanly to bits 0-8.

Ignoring String Allocation Overhead

Creating hundreds of string objects inside the nested loop in high-throughput production code.

Crucial Edge Cases to Validate:

  • Completely Empty Board ('.' everywhere) — Must return true immediately as no duplicate constraint is violated.
  • Duplicate in 3x3 Box but Different Rows and Cols — e.g. (0, 0) = '8' and (1, 1) = '8'. Row and col checks pass independently, but boxes[0] correctly flags the collision and returns false.
  • Fully Solved Valid Board — All 81 cells filled with valid digits -> returns true.
  • Invalid Board with Unsolvable Configurations — A board might have no duplicates among existing numbers but still be mathematically impossible to solve. The problem specifies only validating existing filled cells, so it must return true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify validity vs solvability: Explicitly tell the interviewer "We are checking if the current board is valid, not if it has a complete solution."
  2. Explain the box formula clearly: Write down (r / 3) * 3 + (c / 3) and test it on corner cells like (0, 0), (4, 7), and (8, 8).
  3. Highlight the Bitmasking optimization: Demonstrating how 9-bit integers replace Hash Sets shows deep systems programming awareness.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Which 3x3 box does cell (row = 4, col = 7) belong to?

2.Why does Valid Sudoku have O(1) time and O(1) space complexity?

3.If a partially filled board has no duplicates in any row, col, or 3x3 box, but is mathematically impossible to complete, what should the function return?

Back to DSA Sheet