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.

MediumArray Hash Table Matrix21 min readAsked at: Amazon, Microsoft, Apple +23

Practice this problem

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:

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.

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.

Code

Python C Java C++C#JavaScript

Python

Java

C++

JavaScript

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.

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).

Code

Python C Java C++C#JavaScript

Python

Java

C++

JavaScript

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.

Code

Python Java C++Go TypeScript Rust JavaScript C#PHP

Python

Java

C++

TypeScript

Rust

JavaScript

PHP

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	—

Detailed 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)

Video Solution

Valid Sudoku - Amazon Interview Question - Leetcode 36 - Python • NeetCode • 536,717 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Valid Sudoku with our built-in code editor and test cases.

Practice on FleetCode

Check if Every Row and Column Contains All Numbers

Sudoku Solver

Problem Info

DifficultyMedium

Acceptance64.9%

Approaches3

Reading time21 min

Asked at

Amazon Microsoft Apple Goldman Sachs Meta

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach 1: Hash Set Validation

Code

Complexity

Approach 2: Approach 2: Bit Manipulation

Code

Complexity

Approach 3: Traversal once

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents